🤖 AI

MEMAUDIT: An Exact Package-Oracle Evaluation Protocol for Budgeted Long-Term LLM Memory Writing

The paper introduces MEMAUDIT, an exact package-oracle evaluation protocol that isolates and certifies the quality of long-term LLM memory writing under storage budgets by transforming memory selection into a finite, auditable optimization problem with exact solvers, thereby disentangling representation quality from downstream retrieval and reasoning effects.

Original authors: Nishant Bhargava, Rodrigo Sobral Barrento

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nishant Bhargava, Rodrigo Sobral Barrento

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery that spans months. You have a notebook, but it's small. You can't write down every single thing you see, hear, or do. You have to decide: What do I write down, and how do I write it? Do I copy the whole conversation? Do I just write "Client likes pizza"? Do I write "Client changed their mind to sushi"?

If you write the wrong thing, or write it in a way that takes up too much space, you might fail the case later. But if you fail the case, how do you know why? Did you forget the clue? Did you write the clue down but in a code no one could read? Or did you write the right clue, but the detective who reads the notebook later just didn't understand it?

This paper introduces a new way to test memory systems called MEMAUDIT. It's like a strict, fair referee that only watches the part where you write the notes, ignoring everything that happens later.

The Problem: The "Black Box" of Memory

Usually, when we test AI memory, we ask the AI a question at the end and see if it gets the answer right. The problem is that this is a "black box." If the AI gets the answer wrong, we don't know if it's because:

It didn't save the right memory.
It saved the memory but in a format that was too big or messy.
It saved the memory, but the "search engine" couldn't find it.
It found the memory, but the "thinking brain" ignored it.

The paper argues we need to stop guessing and start measuring the writing phase specifically.

The Solution: The "MEMAUDIT Package"

The authors created a controlled experiment called a MEMAUDIT Package. Think of this as a simulation game with fixed rules:

The Story (Experience Stream): You are given a specific, frozen story of events (e.g., "User said they like vegetarian food, then later said they are now pescatarian").
The Options (Candidate Memories): For every event, you are given a list of possible ways to write it down:
- Raw Span: Copy the whole sentence (Expensive, takes lots of space).
- Fact: Just "Likes vegetarian" (Cheap, but might be outdated).
- Update: "Changed to pescatarian" (Medium cost, very useful).
- Tombstone: "Old vegetarian fact is now invalid" (Crucial for avoiding mistakes).
The Budget: You have a strict limit on how much space you can use (like a small backpack).
The Goal: You must pick the best combination of notes to fit in the backpack so that if someone asks a question later, the answer is supported by what you wrote.

The "Oracle" and the Score

The paper uses a super-smart computer (an "Oracle") to solve this puzzle perfectly. It calculates the absolute best possible score you could get with that specific backpack and those specific story events.

Then, it tests different AI memory systems to see how close they get to that perfect score.

The Score: If the perfect score is 100 and an AI gets 80, we know exactly how much "semantic value" (useful truth) it preserved.
The Magic: Because the rules are frozen, if an AI scores low, we know for a fact it failed at writing, not at searching or thinking.

Key Findings (The "Aha!" Moments)

The paper tested this on several types of memory systems and found some interesting things:

The "Density Trap": Some systems try to be efficient by picking the "cheapest" note per word. The paper shows this is a trap. A system might pick a cheap note that misses the most important detail (like the fact that a user changed their mind), leading to a low score.
The "Tombstone" Importance: In stories where facts change (like the vegetarian-to-pescatarian example), the best memory systems are the ones that write "This old fact is dead" (a tombstone). Systems that only write "facts" and forget to mark old ones as invalid fail the test.
Real-World Systems: They tested real memory tools (like Mem0, Letta, and A-Mem).
- Some systems were great at finding good information to write down (high "extraction" score) but bad at choosing what to keep when the backpack got full (low "selection" score).
- Others wrote notes that were too long and messy, so they couldn't fit the most important facts into the small budget.

Why This Matters

Think of MEMAUDIT as a quality control inspector for a factory.

Before, we just checked if the final car (the answer) drove well.
Now, MEMAUDIT opens the hood and checks the engine assembly line (the memory writing).

It tells engineers: "Your engine is fine, but your workers are putting the wrong parts in the box," or "Your workers are picking great parts, but they're packing them too loosely."

By separating the "writing" problem from the "searching" and "thinking" problems, this protocol helps developers fix the exact part of their AI that is broken, rather than just guessing. It turns a vague "the AI is bad at memory" into a specific "the AI is bad at deciding which memories to keep under a budget."

Technical Summary of MEMAUDIT

Problem Statement
Long-term LLM agents face the challenge of compressing streams of past interactions into persistent memory before future queries are known. Existing evaluation protocols typically measure final question-answering (QA) accuracy. The authors argue that this approach is flawed because it entangles three distinct failure modes: memory writing (selection and representation), retrieval, and reader reasoning. A system may fail because it stored the wrong memory, because the retriever missed a good memory, or because the reader ignored the evidence; final QA accuracy alone cannot isolate which layer failed. Furthermore, deployed systems often store items in forms too expensive for the target budget or fail to select the optimal representation (e.g., raw span vs. extracted fact vs. tombstone) from a set of candidates.

Methodology: The MEMAUDIT Protocol
The paper introduces MEMAUDIT, an exact package-oracle evaluation protocol designed to evaluate the memory writing layer in isolation. The core unit of evaluation is the MEMAUDIT package, which transforms the memory selection problem into a finite, auditable optimization problem with a certified denominator.

Package Definition: A package $P$ is defined by a fixed experience stream, a set of candidate memory representations (e.g., raw text, facts, summaries, tombstones), storage costs, semantic evidence units, future-query requirements, and a storage budget $B$ .
Feasibility Constraints: The feasible memory store $X$ $X$ must satisfy two constraints:
1. Knapsack Constraint: The total cost $\sum c_u \le B$ .
2. Partition Matroid Constraint: At most one representation is chosen per experience ( $|X \cap G_i| \le 1$ ), forcing a choice of representation rather than keeping all variants.
Objective Function: The utility of a store is defined by a concave-over-modular semantic coverage objective:
$F(X) = \sum_{r \in R} w_r h_r \left( \sum_{u \in X} a_{ur} \right)$
Where $R$ are evidence units, $w_r$ are importance weights, $a_{ur}$ is the coverage of unit $r$ by memory $u$ , and $h_r$ is a concave, non-decreasing function (defaulting to $\min(1, z)$ ). This structure ensures diminishing returns for duplicate coverage of the same evidence unit.
Exact Optimization: The protocol computes the exact package optimum ( $OPT_P(B)$ ) using branch-and-bound solvers and certifies results with Mixed-Integer Linear Programming (MILP). This provides a ground-truth denominator against which any writer can be scored.
Union Denominator for External Systems: To evaluate real-world systems (like Mem0, Letta, A-Mem) that may generate memories outside the predefined candidate set, the protocol uses a union package. Exported memories are added as first-class candidates with adjudicated coverage rows. The score is the ratio of the system's achieved utility to the optimal utility achievable by any subset of the union (original candidates + system exports). This distinguishes between extraction quality (how much useful content was found) and selection quality (how well it was chosen under budget).

Key Contributions

Definition of a Finite Package Oracle: The paper defines a rigorous framework for budgeted memory writing with a reproducible, certified denominator, separating write-time quality from downstream retrieval and reasoning.
Semantic Coverage Structure: It instantiates a known concave-over-modular submodular coverage structure to model semantic memory preservation, explicitly handling validity states (e.g., tombstones for invalidating old facts) as positive evidence units rather than negative penalties.
Exact Solvers and Baselines: The authors provide exact package optima via branch-and-bound and MILP certification. They introduce a Group Value-Threshold (GVT) reference baseline that uses exact marginals to calibrate the system, and demonstrate that density-only heuristics can be arbitrarily bad.
The MEMAUDIT Suite: A release of datasets and tools including:
- Controlled Exact Packages: Synthetic environments (MEMAUDIT-Small) with hidden event graphs to test representation choices.
- Validity-Heavy Stress Tests: Scenarios specifically designed to test the preservation of current truth versus stale facts (e.g., update chains, temporal intervals).
- Natural and Exported Packages: A human-audited "Natural-87" subset derived from realistic conversation slices, and exported memory stores from Mem0, A-Mem, and Letta evaluated under the same protocol.

Results

Separation of Layers: In controlled experiments, MEMAUDIT successfully isolates representation quality. For instance, a "density-only" heuristic (choosing the highest value-per-cost item) systematically fails to preserve validity-state units (tombstones), achieving only 26–36% of the exact OPT on tight budgets, whereas the GVT baseline remains near optimal.
Importance of Validity Candidates: Removing tombstone/compound-update candidates from the candidate set reduces the maximum achievable utility (OPT) by significant margins (e.g., dropping to ~52–81% of full OPT depending on budget), proving that candidate generation bottlenecks are distinct from selection bottlenecks.
External System Diagnostics: When applied to exported stores:
- Mem0: Shows a high "upper-pruned" bound (indicating good extraction of useful evidence) but a lower selected-store ratio, identifying budget-aware selection as the primary bottleneck.
- Letta: Achieves strong salience-pruned union ratios, indicating effective selection of relevant content.
- A-Mem: Preserves evidence in rich notes, but the serialized size often exceeds strict budgets, resulting in a zero score for full-store views unless compacted.
Stability: The protocol is robust to cost model variations (e.g., word count vs. byte-overhead) and annotation noise, with human-validated labels preserving rankings compared to model-adjudicated labels.

Significance and Claims
The paper claims that MEMAUDIT provides a necessary diagnostic tool for the memory writing layer that end-to-end QA cannot offer. By freezing the candidate set, costs, and evidence units, it answers the specific question: "Given this package, how much of the package-feasible semantic value did the writer preserve?"

The authors emphasize that this is a write-time diagnostic, not a replacement for end-to-end assistant evaluation. Its significance lies in:

Localization: It pinpoints whether failures stem from candidate generation, representation choice, or budget-aware selection, rather than conflating them with retrieval or reader errors.
Reproducibility: It offers a deterministic, auditable denominator (the exact OPT) rather than relying on stochastic downstream QA.
Comparability: It allows heterogeneous systems (with different internal representations) to be scored on a shared semantic ground truth via the union denominator.

The paper remains modest, noting that Natural-87 is a "first audited natural package" and support-sliced, intended for diagnostics rather than as a final full-haystack benchmark. It does not claim to solve the entire long-term memory problem but provides the "exact package oracle" needed to evaluate the compression and selection components rigorously.