Why agent memory should be an append-only log

The first time I had to give an agent durable, long-term memory, one requirement kept nagging me: what happens when someone says “delete everything you know about person X”?

With a normal mutable store, the honest answer is “we’ll try”. With the design I ended up with, the answer is “here’s a proof”, scoped to the derived state the agent actually queries. This post is about the difference, including exactly where the proof’s boundary sits.

The problem with mutable memory

The obvious way to give an agent long-term memory is a table or a graph you update in place. The agent learns a fact, you upsert a row. The fact changes, you overwrite it. Simple.

It breaks down in three ways:

Provenance is lost. The moment you overwrite a fact, you can no longer answer “how does the agent know this?” The old value and its source are gone. For an agent that acts on what it remembers, that’s a real problem: when it does something surprising, you want to trace the memory back to the document or conversation that produced it.
Deletion is a hope, not a proof. PII doesn’t stay in one row. It gets summarized, merged into derived facts, embedded, cached. When a deletion request comes in, you delete the rows you can find and hope the data didn’t propagate somewhere you can’t trace. “We deleted it” becomes a statement of effort, not a statement of fact.
Concurrent updates race. Two ingestion paths learn conflicting things about the same entity at the same time, and last-write-wins silently eats one of them.

All three are symptoms of the same root cause: the store is authoritative. Whatever is in the table right now is the truth, and history is whatever you remembered to log on the side.

Flip it: state is derived, the log is the truth

The design that fixes this inverts the relationship. Facts are never edited in place. They are only appended as events, each carrying provenance (which document, which chat, which ingestion run it came from). The current state the agent actually queries is a fold over that log: a reduction that replays events in order and produces the derived graph. Concretely, mine uses an LLM to extract fact triplets (subject, relation, object) from each event’s content and merge them into the graph, and later roll-up passes derive new relationships from facts already present. The property that matters is that the fold is input-closed: it reads the log and nothing else. Everything the extraction model ever sees is assembled from log events.

   APPEND-ONLY LOG (immutable, ordered)          INPUT-CLOSED FOLD
   ┌──────────────────────────────────┐
   │ e1  fact A     (src: doc#1)       │              fold()
   │ e2  fact B     (src: chat#7)      │   ──────────────────────►   ┌──────────────┐
   │ e3  fact A'    (src: doc#3)       │   reads ONLY the log        │ CURRENT      │
   │ e4  ...        (provenance kept)  │                             │ STATE        │
   └──────────────────────────────────┘                             │ (derived)    │
                                                                     └──────────────┘
   PII erasure:
     remove source events for subject X   ─►  re-fold  ─►  state provably free of X
     (state is a function of the log, so nothing survives the removal)

If you’ve done event sourcing on the service side, this is the same discipline applied to agent memory. But the payoff here is bigger than auditability.

Erasure becomes structural

Here is the part I care about. Because the derived state is a pure function of the log, erasure stops being a search-and-destroy mission and becomes a two-step operation:

Remove the source events for subject X from the log.
Re-run the fold.

That’s it. The new state cannot contain X’s data, because the fold’s only inputs are the remaining events, and none of them carry it. X’s data never enters the model’s context at all. You don’t have to trace where the data propagated inside the graph. You don’t have to enumerate every derived fact, summary, or merge that touched it. The re-folded state is a valid memory derived entirely without X.

Compare the two guarantees:

  MUTABLE STORE                        APPEND-ONLY LOG + FOLD
  "we deleted the rows we found"       "state = fold(log)"
  + hope nothing propagated            log has no X, so fold(log) has no X
  = effort                             = proof

This is the shift from a property you enforce (delete carefully, everywhere, forever) to a property that is structural (the design makes the violation inexpressible).

The other two problems fall out for free

Once state is derived, the remaining weaknesses of mutable memory disappear without extra machinery:

Provenance is intact by construction. Nothing is overwritten, so every fact in the derived graph traces back to the events that produced it. When the agent asserts something, I can walk back to doc#1 or chat#7 and see exactly why.
State is reproducible, to the extent the fold is. A symbolic fold gives you the same graph for the same log, every time. With an LLM in the fold (mine uses one to extract and consolidate facts) you get stability rather than identity, and the guarantees in this post rest on closure, not on replay being bit-identical. Debugging stays sane either way: every fact traces to inspectable events.
Concurrent learning doesn’t race. Two ingestion paths appending at the same time just produce two ordered events. The fold decides how they combine, in one place, explicitly, instead of last-write-wins deciding it implicitly.

This kind of memory graph pairs naturally with a RAG layer (ingestion, embedding-and-rerank retrieval with permission-aware scoping), so an agent’s retrieval and its long-term memory share one story about where knowledge comes from and how it leaves.

Caveats, honestly

This isn’t free, and the proof has edges worth stating plainly.

The load-bearing property is input closure, not determinism. An early version of this argument leaned on the fold being a pure function. In practice my fold uses an LLM, and an LLM step is not deterministic no matter how well you tune the prompt. The erasure guarantee survives anyway, because it never needed determinism: it needs the fold to read the log and nothing else. If X’s events are gone and the fold’s only inputs are the remaining events, the output cannot contain X’s data, however nondeterministic the model is. What nondeterminism does cost is identity: you get a valid state derived without X, not the bit-identical state “as if X never existed”. Closure also has to be enforced mechanically, not by convention: everything the fold hands the model, including retrieval context and few-shot examples, must be recorded as an input. Undeclared retrieval quietly breaks the proof.

Erasure edits the log, which bends “append-only”. Removing events is a mutation of the one structure I called immutable, and it does nothing about backups (you have backups). The variant that preserves both is crypto-shredding: encrypt each subject’s events under a per-subject key and destroy the key to erase. The log stays untouched and every backup goes dark for that subject at the same moment. Be honest about what it buys, though: it shrinks the deletion problem from “every copy of the data” to “every copy of the key”. Much smaller, not zero, and key destruction is itself an operational act.

The proof covers the derived graph, not the universe. Embeddings in the retrieval index, rerank caches, snapshots taken before the erasure, and anything exported (a fine-tune, a copy someone made) live outside the fold and still need enumeration and deletion the old-fashioned way. So does the LLM API the fold calls: X’s data rode along in those requests on every fold run before the erasure, so provider-side logs and retention are part of the operational list too, governed by the provider’s deletion terms rather than yours. The one-line honest version of this design: erasure is structural for the derived state, and operational for everything downstream of it. That is a far smaller operational surface than a mutable store leaves you with. It is not zero.

Re-folding costs compute proportional to the log, so you want snapshots and incremental projection for the common path, with the full re-fold reserved for erasure and recovery.

Takeaway

If your agent’s memory is a mutable store, “delete this person’s data” is an operational promise you have to keep everywhere, forever. If memory is an append-only log and state is an input-closed fold over it, the core of that promise becomes an equation: state is a function of the log alone, so removing the source events and re-folding provably removes the data from everything the fold produces. What remains operational (indexes, snapshots, backups) is a short, enumerable list instead of the whole system.

Make state derived, never authoritative. Provenance, reproducibility, and provable erasure stop being features you build and start being consequences of the shape.