Certified Workflow Memory: Admitting Only Authorized Traces into Agent Memory

Agents that remember how they solved past tasks get much better at new ones. Agent Workflow Memory turns successful runs into reusable routines and raises WebArena success from 23.5% to 35.5%. These systems store any run judged "successful" by an automated evaluator, and success is not the same as authorization. MasDrift finds unauthorized-action rates of up to 19.8% in multi-agent hierarchies whose task completion reaches 98.6%. An agent that finished a task by an unauthorized shortcut, such as sending an invoice the user said only to draft, writes that shortcut into memory, and every later task that retrieves it inherits the violation.

We propose to attach an authorization certificate to each memory unit at the moment it is stored, and to check that certificate again against the new user's request when the unit is retrieved. The certificate is a hash-linked record showing that each step in the source run traced back to the user's instruction. It also records, for each abstracted variable in the routine (for example {recipient}), whether its value came from the user or from untrusted retrieved content. Runs that fail the chain check never enter memory. Retrieved routines can only fill sensitive variables from sources of the same trust class as in the certified original. The checks are deterministic hashing, so they add almost nothing to the cost of retrieval.

Core Claim

Authorization should be enforced when memory is written and when it is reused, not only when a tool is called. A runtime gate on its own cannot keep a self-improving memory clean. It can block a poisoned action, but the poisoned routine stays in memory and keeps proposing the blocked path. That produces repeated failures and, under trust-degradation policies, lockouts. We claim that certifying memory at the point of writing keeps most of the task-success gains of workflow memory. We also claim it stops the violation rate from growing as memory accumulates online, which is the "snowball effect" of AWM working in reverse.

The mechanism reuses Same Action, Different Justification. That paper introduces Causal Chain Authorization (CCA), a gate that checks four things before an irreversible tool call: a signed user origin, hash-linked reasoning and observation steps, no skipped steps, and agreement with an independent audit log. On its matched-pair benchmark, CCA reaches 100% pairwise authorization separation accuracy at 0.1 ms median latency. The recursive hash structure comes from network path validation, where SDNsec chains each hop's authentication code into the next so that valid segments from different paths cannot be spliced into a forged shortcut. That splicing is exactly the risk of stitching together memory units drawn from different runs.

CCA leaves two things open. First, it says nothing about memory. Second, it names content integrity as an explicit limitation: a hash-valid chain can still carry a payload altered by injected text. Our per-variable provenance tags address one tractable slice of that limitation. They do not catch every altered payload. They do catch a sensitive argument whose value originated in retrieved content when the certified routine expects it to come from the user. This makes concrete the "semantic taint" that SoK: Trust-Authorization Mismatch proposes in theory without implementing.

Relation to Prior Work

Workflow memories supply the substrate we modify: AWM, LEGOMem with its modular plan and subtask units, and H-EPM with its tool-transition graph. All three assume that past successes are benign, and none checks integrity. AWM itself concedes that its online mode depends on fallible evaluators.

PoU is the closest work in spirit. It verifies that a research agent actually used the evidence it retrieved, using perturbation rewards during reinforcement-learning training. It differs from our proposal in three ways. It works on flat question-answering passages rather than procedural memory. It runs at training time with an LLM judge rather than as a deterministic check. And it does not concern authorization.

MasDrift constrains our design. It shows that passing narrowed permissions down a hierarchy costs up to 36.3 points of completion, while checking against a central record of the root request costs only 1.6 points. Our certificates therefore bind each unit back to the current root request at retrieval time. They do not attenuate permissions hop by hop.

Retrieval-overhead work acts as a constraint on the design rather than a component of it. TARG shows that retrieval can be skipped 70–90% of the time without losing accuracy, and it treats gating cost as the thing to minimize. Our check must add negligible latency on top of memory lookup. We also test whether filtering at admission shrinks the memory store and the number of candidate units enough to reduce retrieval cost.

Research Program

We will build a memory layer that sits underneath AWM-style and LEGOMem-style induction. Every agent run is logged as a CCA chain.

At induction, a unit is admitted only if its full source chain passes the four CCA checks and every irreversible action in it maps to an intent category allowed by the original request, following CCA's compatibility matrix. When the induction step abstracts a concrete value into a variable, it also records that value's origin class: user-signed, system, tool output, or retrieved web or document content. The certificate is a hash over the abstracted step sequence, the intent category, and the origin classes.

At retrieval, the unit is re-bound to the current request. Its intent category must be compatible with the new request's origin, and at execution time each sensitive variable may only be filled from an origin class no less trusted than the certified one. A unit whose certificate fails re-binding is withheld from the agent's context, not just blocked at call time.

The research questions are these. Does admission filtering stop the unauthorized-action rate from growing over an online stream of tasks? How much of the success gain from memory does it keep? Does it avoid the lockouts that a runtime-only gate causes? Which injected-content attacks does provenance tagging catch, and which does it miss?

Baselines

The naive reference point is the agent with no memory, run under the CCA runtime gate. It fixes the success rate we must beat, which is the benefit of memory at all, and the violation floor, which is the cost.

The strongest competitor on task success is unfiltered workflow memory. That means AWM on WebArena and LEGOMem on OfficeBench, run with the same backbone models, the same task streams and order, and the same retrieval budget. The reported numbers are AWM's 35.5% WebArena success and LEGOMem's 50.22% OfficeBench success for a GPT-4o orchestrator with GPT-4o-mini agents. Our first step is to reproduce these numbers in our harness on the clean streams. On poisoned streams, we will count ourselves as beating unfiltered memory if we are within a few points of its success rate while holding a substantially lower and non-growing violation rate. We found no reported result on Lacuna for any workflow memory under poisoned or authorization-violating trace streams.

The strongest competitor on safety is unfiltered memory combined with the CCA runtime gate. It uses the same CCA implementation and the same trust-degradation policy, and differs from our method only in where checking happens. Beating it means higher completion and fewer lockouts at an equal or lower unauthorized-action rate.

We also run memory filtered at admission by an LLM judge that reads the full trace. It gets the same judge model and prompt-tuning budget that we give our own thresholds. For this baseline, CCA reports 0% on scope and chain-verifiability tests and more than 500 ms of latency.

Two ablations isolate the key ingredients. The first uses chain certificates without per-variable provenance. The second uses provenance tags without chain verification at admission.

Why not just…?

Why not just keep the runtime CCA gate and leave memory alone? This is the most serious alternative. On authorization violations alone it may come close to our method, because it blocks unauthorized irreversible calls whatever their origin. The difference we expect lies in completion and stability. A poisoned routine keeps being retrieved, and CCA's monotonic trust degradation reaches the UNTRUSTED state by the fifth failed attempt, so the gate can lock out the very tasks the memory was meant to help. The gate also cannot see parameter tampering inside an authorized call. Our head-to-head comparison measures completion, lockout rate, and violations caught only by provenance tags. If runtime-only matches us on all three, the proposal reduces to "CCA suffices," and we will report that.

Why not just have an LLM judge vet traces before storing them? CCA reports that LLM judges score 0% on chain verifiability and lean toward allowing actions when a chain cannot be verified. Admission-time vetting would inherit that bias and be applied to every stored run. We still run this baseline, because judging a completed trace offline is an easier setting than judging at runtime and could in principle do better.

Why not just exclude any trace containing an irreversible action from memory? It is simple and it is safe. But irreversible steps (send, pay, deploy) are exactly where OfficeBench and τ-bench tasks fail, and dropping them discards those routines. We run this baseline. If it keeps most of the success gain, the certificate machinery is not worth building.

Proposed Experiments

We will build poisoned online streams from three sources. The first is τ-bench retail and airline (τ-bench), where the reported GPT-4o pass^1 is 61.2% and 35.2%. The second is OfficeBench. The third is MasDrift tasks, which pair each task with reserved actions and explicit constraints.

In a controlled fraction of early tasks, we insert injected instructions into tool outputs or documents, in the style of the in-code comments used by CCA. We then vary the injection rate and the length of the stream.

The metrics are task success (pass^1 and pass^k), unauthorized-action rate, constraint loss (MasDrift's definitions), lockout rate, the number of poisoned units present in memory over time, and the latency added per retrieval.

The decisive check is the curve of unauthorized-action rate against stream position. Unfiltered memory should rise as poisoned routines are reused, and certified memory should stay flat. A second check compares completion and lockouts between certified memory and runtime-only CCA. A third check uses a held-out suite of injection types, including injections that alter a value whose certified origin class is itself untrusted. Provenance tags should miss these by design, and reporting them bounds how much of the content-integrity gap we actually close.