Note 2
Memory with Receipts: A Belief Ledger for AI Agents
When an agent starts a new session, it spends time re-establishing what it already knew: it re-searches a codebase it mapped yesterday and re-verifies a paper it confirmed last week. This note sets out our working design for a belief ledger, which stores every fact with the evidence that made it true, re-checks that evidence at session start, and gives the agent a list of what went stale.
- Published
- 2026-09-06
- State
- Working design
- Sections
- 6
The context tax
An agent spends a large share of every session re-establishing facts it had already established. People spread that cost over months in the same job, whereas an agent pays it again at the start of every session.
Take a coding agent at the start of a session. It greps (searches the raw text) for the function it found yesterday, because the map it made of the codebase went with yesterday's context window. It re-opens the config file to confirm a flag it has already confirmed twice this week. It searches the web for a paper ID it verified last Tuesday, because from the inside, a verified ID and a remembered ID look identical. All of this work produces no new output. It's the cost the agent pays to trust its own footing again, and it's what we mean by the context tax.
Some of the tax is structural. A model cannot hold its full working history in the window, so state gets paged in and out of external storage. Packer et al. make the operating-system analogy explicit and manage context the way an operating system swaps memory to disk when RAM runs out [1]. Paging solves the capacity problem. It leaves the trust problem where it was, though, because what comes back from storage is exactly as old as the moment it was written.
So every session boundary forces the same decision. The agent can trust last week's note and risk acting on a world that has moved on, or it can re-derive everything from scratch and spend the first half hour proving things that were already proved. Engineers face that decision after a long holiday, a few times a year, whereas an agent faces it at the start of every session.
- Evidenced
Context windows are a hard resource limit: an agent cannot carry its full working history in-context, so systems page state between the window and external storage. [1]
- Proposed
In long-running agent work, the dominant cost is re-establishing what is true, ahead of generating new output.
- Proposed
At every session boundary an agent chooses between trusting old notes and re-checking everything, with no way to tell how risky either choice actually is.
Memory without receipts
The agent-memory literature has several good systems for storing beliefs. Each stores the conclusion alone, with no evidence attached and no re-check before reuse.
The memory literature has good answers for where beliefs should live. MemGPT pages them between fast and slow tiers [1]. Reflexion has the agent write itself a note about what went wrong and read it back before the next attempt [2]. Park et al.'s generative agents record everything they experience into a memory stream, then periodically compress it into higher-level reflections that drive planning [3]. Voyager banks whole skills: executable code that worked once, kept for reuse [4].
If you look at what each system stores, though, it's always the conclusion. The belief is kept and the reason it was believed is left behind. For example, a stored reflection might say "the test suite lives in tests/unit". The record doesn't say which directory listing established that, or when, or how to check it again for less than the cost of re-deriving it. Recall answers the question "what did I believe", and the loop has no step that asks "is it still true".
Voyager's skill library comes closest. Each library entry was verified by execution at the moment it was written [4]. That verification holds for the world as it was at the time, though, and the world the skill runs against next month may have changed.
- Evidenced
MemGPT manages tiered memory the way an operating system manages virtual memory, paging context in and out of the window. [1]
- Evidenced
Reflexion agents write themselves notes about what went wrong and read them back before the next attempt. [2]
- Evidenced
Generative agents record experiences in a memory stream, synthesise them into higher-level reflections, and retrieve them to plan behaviour. [3]
- Evidenced
Voyager accumulates a persistent library of verified executable skills and reuses them across tasks. [4]
- Proposed
Across these systems, recall answers the question 'what did I believe' and never the question 'is it still true'.
The belief ledger
Our design call: record every assertion an agent relies on together with the evidence that made it true, re-verify the evidence cheaply at session start, and hand the agent a diff of what went stale.
Our design call is a ledger. Every fact the agent relies on becomes an entry with two halves: the assertion, and the evidence that made it true. "The test suite lives in tests/unit" plus the hash of the directory listing that showed it. "This arXiv ID resolves to this paper" plus the check against the live record and the date it ran. "The build passes" plus the commit it passed at.
The benefit shows up at session start. In place of rebuilding its picture of the world, the agent checks the receipts again: it hashes the files, re-requests the URLs (just asking each server whether anything changed, without downloading the page) and compares the type signatures. These are cheap checks that run in bulk, and most of them come back unchanged. What the agent receives is a diff, for example: forty beliefs still hold, three went stale, and one lost its source entirely. The agent reviews the three, stops relying on the one, and gets on with the work.
It's worth pointing out that the check only has to notice that the evidence moved. Working out the new truth is a separate job. A hash mismatch doesn't say what changed, and for this purpose it doesn't need to: "this belief is no longer backed" is enough to tell the agent where to look first, and knowing where to look is most of the value.
- Proposed
A recorded belief should carry evidence a machine can re-check: a file hash, a commit id, an HTTP check, a type signature.
- Proposed
Most staleness is detectable without re-reading the source, because the check only has to notice that the evidence changed; it can leave the belief itself alone.
- Proposed
A staleness diff turns session start from re-derivation into review: confirm the flagged beliefs, trust the rest.
The pattern is older than agents
Software engineering already uses this pattern. Lockfiles pin dependencies to hashes, content-addressed stores make staleness impossible to hide, and a recent security design, CaMeL, applies verify-before-trust to agent control flow.
Software engineers will recognise this pattern. A lockfile is a belief ledger for dependencies: the claim "this package at this version" recorded next to a hash, so that every install verifies the package against it. Content-addressed stores go further and make the name the fingerprint, so a stale copy cannot even be asked for by name. Reproducible builds pin the whole toolchain the same way. Wherever silent drift has caused problems in software, the fix has converged on the same design: keep the claim next to a checkable fingerprint, and make checking cheaper than trusting.
Agent security is arriving at the same place from a different direction. One security design, CaMeL, works out the program's plan from the trusted request before any untrusted data is read, so whatever a poisoned email says, it cannot steer what the agent does. Debenedetti et al. report solving 67% of AgentDojo tasks with provable security that way [5]. The principle carries over directly: when the system can check something, it should check it in place of trusting what a model remembers or reads.
A belief ledger applies the same principle to a third target. CaMeL protects the inputs and lockfiles protect the dependencies, while the ledger protects the worldview: the accumulated beliefs an agent acts on, which today are the least checked part of the whole stack.
- Evidenced
CaMeL extracts control and data flow from the trusted query so that untrusted data an agent retrieves can never steer the program, and its authors report solving 67% of AgentDojo tasks with provable security. [5]
- Proposed
Lockfiles, content-addressed storage and reproducible builds are all the same design: record the claim next to a checkable fingerprint, then verify instead of trusting.
- Proposed
A belief ledger applies that design to an agent's worldview, where earlier uses applied it to inputs and dependencies.
What a ledger cannot check yet
Three gaps: checking what code does as well as what it says, knowing how often to re-check, and handling beliefs that arrive from another agent. Then the small testbed we would like to run against all three.
Checking what code does
A file hash confirms a file is unchanged, and a request to arxiv.org confirms a paper still exists. Checks like these cover facts about what things are, and they're cheap. However, most of the beliefs an agent actually acts on are about what things do: this function retries when a call fails, this endpoint copes with a missing field. The only real evidence for behaviour is running the code, and so far no published approach does that cheaply enough to repeat at the start of every session.
How often to re-check
If the agent re-checks every belief at every session start, the ledger costs as much as the re-deriving it was meant to replace. If it re-checks too rarely, the ledger is back to being stale memory with better records. Different facts go stale at very different speeds (a language standard barely moves; a feature branch moves daily), and the published record has no good rule yet for matching the check to the speed of change.
Beliefs that arrive from other agents
Du et al. and Fu et al. have agents passing internal states to each other directly, with no text in between [6],[7]. This is useful, but it changes what the receiver ends up holding: a belief it absorbed from another model, with no document behind it. There's no source to hash and no page to re-check. The channel delivers the conclusion without the reason to trust it, so a ledger has nothing to attach a receipt to. Our latent-space note covers the security side of that channel. This is the memory side, and it is an open problem too.
The testbed we want to run
Each gap above can be measured. The rig we have in mind is small: wire a plain file-and-URL ledger into a working coding agent (file hashes, commit ids, one HTTP check per external fact), let it run through a few weeks of real sessions, and count three things. Firstly, how many recorded beliefs actually go stale between sessions. Secondly, what the session-start re-check costs compared with re-deriving everything from scratch. Thirdly, how often a stale belief would have steered the agent wrong if the ledger hadn't caught it. Those three numbers would turn this note from a design argument into a result, whichever way they come out. As with our latent-space testbed, we'll link the repo from this page once there is one worth cloning.
- Open problem
Cheap checks cover what things are (a file's hash, a paper's existence); no published approach verifies what code does cheaply enough to run at every session start.
- Open problem
The published record has no good rule yet for how often each kind of fact should be re-checked, matched against how fast that kind of fact actually changes.
- Evidenced
Agents can already pass internal states to each other directly, with no text transcript in between. [6],[7]
- Open problem
A belief absorbed from another agent's internal state arrives without a source, so there is nothing for a ledger to re-check.
- Proposed
A small rig, a file-and-URL ledger wired into a working coding agent, would measure staleness rates, re-check cost and prevented mistakes over real sessions.
References
Numbered in the order they are first cited. Each green EVIDENCED marker above links to at least one of these.
- [1]MemGPT: Towards LLMs as Operating Systems
Packer et al. · arXiv 2023
- [2]Reflexion: Language Agents with Verbal Reinforcement Learning
Shinn et al. · NeurIPS 2023
- [3]Generative Agents: Interactive Simulacra of Human Behavior
Park et al. · UIST 2023
- [4]Voyager: An Open-Ended Embodied Agent with Large Language Models
Wang et al. · arXiv 2023
- [5]Defeating Prompt Injections by Design
Debenedetti et al. · arXiv 2025
- [6]Enabling Agents to Communicate Entirely in Latent Space
Du et al. · ACL 2026
- [7]Cache-to-Cache: Direct Semantic Communication Between Large Language Models
Fu et al. · ICLR 2026