Fresh Memory, Stale Plans: Dependency-Scoped Validation for Distributed LLM-Agent Memory

# Dependency-Scoped Validation for Distributed LLM-Agent Memory
Source: [https://arxiv.org/html/2609.03340](https://arxiv.org/html/2609.03340)
###### Abstract

Distributed LLM\-agent teams can read the latest shared facts and still act on an obsolete plan\. A planner may derive an action from requirementr3r\_\{3\}, another agent may commitr4r\_\{4\}, and an executor may receiver4r\_\{4\}without replacing the plan derived fromr3r\_\{3\}\. We call this*stale\-plan execution*: state freshness does not establish that the plan authorizing an action remains valid\. We introducePlanFence, a dependency\-scoped action\-validation protocol\. Plans cite the exact public records they used, and an executor validates only the records that can affect the pending external action, replanning once or blocking when validation is incomplete\. In 30 controlled live workflows with a post\-plan revision, a freshness\-only executor acts on the obsolete plan in every task, whereasPlanFencecompletes all tasks without an invalid action\. Controlled replay reveals two conditional boundaries: proactive synchronization yields lower coordination stall at low churn, whilePlanFenceavoids repeated update\-path coordination as churn grows and avoids validating unrelated state as the shared keyspace grows\. These are controlled safety and systems\-cost results, not general task\-accuracy gains\.

## 1Introduction

Distributed large language model \(LLM\) agent systems increasingly divide a task among specialized roles that plan, retrieve information, and invoke external tools\. Frameworks such as AutoGen, MetaGPT, CAMEL, and ChatDev organize these roles across separate processes or devices\[[25](https://arxiv.org/html/2609.03340#bib.bib14),[11](https://arxiv.org/html/2609.03340#bib.bib15),[15](https://arxiv.org/html/2609.03340#bib.bib16),[18](https://arxiv.org/html/2609.03340#bib.bib17)\]\. Agents may retain private context and local tools while replicating the public task state needed for coordination, making shared memory a first\-class systems concern\[[27](https://arxiv.org/html/2609.03340#bib.bib6),[19](https://arxiv.org/html/2609.03340#bib.bib7),[24](https://arxiv.org/html/2609.03340#bib.bib8)\]\. This separation lets each role operate independently, but it can also separate an external action from the state and plan that authorized it\.

Recent persistent\-world studies show that agent\-authored artifacts and executable programs can outlive their creators and be reused by later agents through a shared environment\[[17](https://arxiv.org/html/2609.03340#bib.bib30)\], making the temporal separation between plan derivation and eventual execution concrete\.

Consider a planner that reads requirementr3r\_\{3\}and derives planp⁡\(r3\)p\(r\_\{3\}\)\. Before execution, another agent commits a revised requirementr4r\_\{4\}\. Background propagation may deliverr4r\_\{4\}to the executor without replacingp⁡\(r3\)p\(r\_\{3\}\), so the executor can call a tool with arguments derived from the old requirement while already holding the new one\. A reservation may use a superseded destination, a fulfillment action may ship a cancelled order, or a deployment may release an obsolete build\. We call this failure*stale\-plan execution*\. The failure is not stale memory at the executor; what remains stale is the derivation that supplied the action’s arguments\. Installingr4r\_\{4\}does not change the fact thatp⁡\(r3\)p\(r\_\{3\}\)was produced fromr3r\_\{3\}, so state freshness alone cannot establish that a pending plan is still authorized\. The executor must instead verify that the plan descends from the current public records on which its action depends\. We call this property*lineage validity*\.

One direct solution is to coordinate public state strongly\. Every owner can broadcast its current record ID and invalidate plans whose exact parents no longer match, or executors can compare those parents through one strong service\[[9](https://arxiv.org/html/2609.03340#bib.bib1),[1](https://arxiv.org/html/2609.03340#bib.bib2),[3](https://arxiv.org/html/2609.03340#bib.bib5)\]\. When this coordination is cheap, it is the simplest safe choice\. Section[3](https://arxiv.org/html/2609.03340#S3)measures when one synchronous public\-state transfer enters the critical path\. The required check, however, is narrower than globally fresh memory: a reservation action depends on its requirement, not on an unrelated catalog record or another workflow’s state\. This creates a systems tradeoff between coordinating early over broad shared state and validating only the records relevant to an action when it is about to execute\.

We evaluate this distinction through three questions:

RQ1:Can an agent read the latest state and still act on an outdated plan?

RQ2:As public state changes more often, which causes less waiting: synchronizing every update or validating only before an action?

RQ3:As shared state grows, when does checking only action\-relevant state reduce coordination cost compared with checking all shared state?

Our Approach\.We separate the safety invariant from the mechanism used to establish it\. The invariant is exact lineage validity at a protected action; the systems choice is when and over what scope to check it\. This separation leads toPlanFence, a dependency\-scoped protocol placed at the action boundary\. Each plan cites the exact public records used to derive it, and a tool wrapper declares which records can affect the pending action\. Before an external call, the executor validates those dependencies with their owners\. A changed input triggers one replan and a second check; an incomplete parent chain, dependency declaration, or owner response blocks the action\.PlanFencecoordinates public records, not private prompts or hidden reasoning\. Figure[1](https://arxiv.org/html/2609.03340#S1.F1)summarizes this action\-boundary gate, from detecting a changed dependency through replanning to the final authorize\-or\-block decision\.

![Refer to caption](https://arxiv.org/html/2609.03340v1/planfence.png)Figure 1:Fresh facts do not guarantee a fresh plan\.A freshness\-only check can observe requirementr4r\_\{4\}while the action still uses planp3p\_\{3\}\.PlanFencevalidates the plan’s declared dependency, detects the mismatch, fetchesr4r\_\{4\}, and permits one replan before it authorizes or blocks the action\.Our main contributions are summarized as follows:

- •We identify stale\-plan execution and formalize lineage validity, distinguishing current executor state from current plan authorization\. In 30 controlled live workflows, the freshness\-only owner\-head check issues an obsolete action in every task, whilePlanFencecompletes all tasks without an invalid action\.
- •We design and implementPlanFencefor distributed agent memory\. Its action\-boundary gate binds plans to exact public inputs, validates only tool\-declared dependencies with their owners, and permits one replan before failing closed\.
- •We compare safe coordination policies under identical schedules and map their coordination\-stall boundary\. Proactive synchronization has lower stall at low update rates;PlanFenceavoids repeated unrelated\-state coordination as updates grow\. Against an equally safe batched all\-key check, it lowers both stall and traffic across the tested 8–128 key loopback and AT&T settings\.

## 2Related Work

#### Provenance and validation\.

Data provenance records which inputs produced a derived object\[[5](https://arxiv.org/html/2609.03340#bib.bib29)\], while optimistic concurrency control validates whether a recorded read set remains current before commit\[[13](https://arxiv.org/html/2609.03340#bib.bib28)\]\.PlanFenceuses the same underlying ideas for a different boundary: a generated plan records its public inputs, and an executor validates them before an external action rather than before a database transaction commits\. Unlike a database transaction, an LLM\-generated plan may persist across role calls, replicas, and state refreshes long after the read that produced it; unless the runtime records exact parents, the executor has no read set to validate at the tool boundary\.

#### Distributed consistency\.

Strong registers, proactive replication, epidemic propagation, and CRDTs offer different ways to expose current replica state\[[3](https://arxiv.org/html/2609.03340#bib.bib5),[9](https://arxiv.org/html/2609.03340#bib.bib1),[1](https://arxiv.org/html/2609.03340#bib.bib2),[7](https://arxiv.org/html/2609.03340#bib.bib4),[20](https://arxiv.org/html/2609.03340#bib.bib3)\]\. Other systems ration consistency or provide application\-level choices between latency and freshness\[[12](https://arxiv.org/html/2609.03340#bib.bib24),[14](https://arxiv.org/html/2609.03340#bib.bib25),[22](https://arxiv.org/html/2609.03340#bib.bib26),[4](https://arxiv.org/html/2609.03340#bib.bib27)\]\.PlanFencedoes not introduce another consistency model\. It specifies which record versions must still authorize the pending action, and it can use either proactive propagation or action\-time owner queries to establish that fact\.

#### LLM\-agent coordination and memory\.

LLM multi\-agent systems organize role collaboration and communication through fixed or learned interaction structures\[[25](https://arxiv.org/html/2609.03340#bib.bib14),[11](https://arxiv.org/html/2609.03340#bib.bib15),[15](https://arxiv.org/html/2609.03340#bib.bib16),[18](https://arxiv.org/html/2609.03340#bib.bib17),[8](https://arxiv.org/html/2609.03340#bib.bib18),[30](https://arxiv.org/html/2609.03340#bib.bib9),[28](https://arxiv.org/html/2609.03340#bib.bib10),[29](https://arxiv.org/html/2609.03340#bib.bib11)\]; MCP and A2A provide interfaces for tools and agent interaction\[[2](https://arxiv.org/html/2609.03340#bib.bib12),[10](https://arxiv.org/html/2609.03340#bib.bib13)\]\. Agent memory research instead emphasizes retrieval, experience, and shared memory\[[16](https://arxiv.org/html/2609.03340#bib.bib19),[26](https://arxiv.org/html/2609.03340#bib.bib20),[6](https://arxiv.org/html/2609.03340#bib.bib21),[21](https://arxiv.org/html/2609.03340#bib.bib22),[23](https://arxiv.org/html/2609.03340#bib.bib23),[27](https://arxiv.org/html/2609.03340#bib.bib6),[19](https://arxiv.org/html/2609.03340#bib.bib7),[24](https://arxiv.org/html/2609.03340#bib.bib8)\]\. Most of this work asks what agents should communicate, retrieve, or retain; persistent\-world systems also study artifacts that survive their creators and acquire executable descent\. SwarmWorld records content\-addressed parent\-child program lineages, lets later agents inherit and modify persistent programs, and commits model\-generated plans as bounded action queues while the shared world continues to evolve\[[17](https://arxiv.org/html/2609.03340#bib.bib30)\]\. Its runtime checks determine whether each attempted action is currently legal under spatial, material, energetic, ownership, and permission constraints\. This technological lineage supports inheritance and attribution;PlanFenceinstead uses exact derivation lineage to determine whether a pending action remains authorized by the current versions of its action\-relevant public inputs, as reported by their owners\.

## 3Motivation and Problem Formulation

Strong coordination can keep public state current, but its placement determines whether communication enters the action’s critical path\. Figure[2](https://arxiv.org/html/2609.03340#S3.F2)measures one authenticated TCP synchronization as payload size, delay, and loss change\. The operation is inexpensive on favorable paths, yet paying it after every dirty update can accumulate substantial delay as content grows or network conditions deteriorate\. Carrier names denote fixed historical traces, not current provider performance\.

Figure 2:One synchronization is inexpensive on favorable paths but can become material as state or link adversity grows\.The blocking time of one fresh authenticated TCP transfer grows with public\-state size under replayed link traces \(a\), while packet loss inflates the p95 for a 4 KiB transfer even when the median remains stable \(b\)\. The 117 ms reference is 10% of the median audited Qwen3\.5 role\-call duration, not an end\-to\-end deadline\. Per\-update synchronization may pay this unit cost after every dirty update; the figure does not compare complete memory policies\.An executor does not need to reproduce an entire memory system at action time\. It needs enough evidence to answer three questions: which public versions produced this plan, which public items can affect this action, and which versions their owners currently authorize\. We introduce the corresponding objects in that order and then state the action\-validity condition\.

### 3\.1Public state has versions

Let𝒜=\{a1,…,aN\}\\mathcal\{A\}=\\\{a\_\{1\},\\ldots,a\_\{N\}\\\}be the agents\. In distributed agent memory, each agent may hold a local copy of the team’s public state\. Private scratchpads, prompts, and hidden reasoning are not public records and lie outside the lineage model\.

A*semantic key*x∈𝒳x\\in\\mathcal\{X\}identifies one logical public item across revisions, while a record ID identifies one immutable version of that item\. The application assignsxxan authoritative ownero⁡\(x\)∈𝒜o\(x\)\\in\\mathcal\{A\}, whose currently authorized record ID is the*head*H⁡\(x\)H\(x\)\. Derived public records retain the exact IDs of the versions used to produce them\.

Figure[1](https://arxiv.org/html/2609.03340#S1.F1)instantiates these objects\. The semantic keyxreqx\_\{\\rm req\}denotes the requirement, and recordsr3r\_\{3\}andr4r\_\{4\}are immutable versions with IDsid3\\mathrm\{id\}\_\{3\}andid4\\mathrm\{id\}\_\{4\}\. After the revision, the owner reportsH⁡\(xreq\)=id4H\(x\_\{\\rm req\}\)=\\mathrm\{id\}\_\{4\}, while planp3=p⁡\(r3\)p\_\{3\}=p\(r\_\{3\}\)still citesid3\\mathrm\{id\}\_\{3\}as its exact parent\. Installingr4r\_\{4\}changes the executor’s local state, but it does not rewrite the derivation recorded byp3p\_\{3\}\.

### 3\.2What evidence must authorize an action?

Exact derivation\.For a protected actionaa, letL⁡\(a\)L\(a\)be the plan root or roots authorizing its arguments\. Immutable parent links record the exact public versions from which those roots were derived\.

Declared scope\.The tool wrapper declaresD⁡\(a\)⊆𝒳D\(a\)\\subseteq\\mathcal\{X\}, the public keys whose values can affect the action\. This declaration belongs to application code rather than generated prose\.

Authoritative currency\.For everyx∈D⁡\(a\)x\\in D\(a\), the executor asks ownero⁡\(x\)o\(x\)for its currently authorized versionH⁡\(x\)H\(x\)\. Starting fromL⁡\(a\)L\(a\), it also follows exact parents until it reaches the version ofxxused by the plan; denote that record ID byFa​\(x\)F\_\{a\}\(x\)\. The mapFaF\_\{a\}is the plan’s*dependency frontier*\. An action is lineage\-valid at the logged validation point exactly when

Valid\(a\)⟺Fa\(x\)=H\(x\),∀x∈D\(a\)\.\\operatorname\{Valid\}\(a\)\\quad\\Longleftrightarrow\\quad F\_\{a\}\(x\)=H\(x\),\\qquad\\forall x\\in D\(a\)\.\(1\)

### 3\.3Why each condition is necessary

Equation \([1](https://arxiv.org/html/2609.03340#S3.E1)\) separates the evidence needed to authorize an action\. RQ1 asks whether reading the latest state is enough to authorize a pending plan\. It is not: a fresh local requirement cannot show which requirement produced a cached plan, whereas the plan’s exact parent does\. For the stale plan,Fa​\(xreq\)=id3F\_\{a\}\(x\_\{\\rm req\}\)=\\mathrm\{id\}\_\{3\}whileH⁡\(xreq\)=id4H\(x\_\{\\rm req\}\)=\\mathrm\{id\}\_\{4\}\. Replanning overr4r\_\{4\}changes the frontier toid4\\mathrm\{id\}\_\{4\}and makes the same check pass\.

RQ2 asks when to pay for owner\-head coordination: after every update or only when an action is about to execute\. A system may distribute authoritative heads proactively or query them at the action boundary, but it cannot infer current authorization from an arbitrary local copy\. RQ3 asks how much state to check\. The declared setD⁡\(a\)D\(a\)contains the action\-relevant state, so a change outsideD⁡\(a\)D\(a\)does not invalidate the action; choosingD⁡\(a\)=𝒳D\(a\)=\\mathcal\{X\}instead recovers all\-key validation\.

The guarantee consequently requires exact binding, action\-time validation, benign authoritative owners, authenticated transport, immutable parent links, and a complete tool\-declaredD⁡\(a\)D\(a\)\. A missing parent, unavailable or malformed owner response, or incomplete declaration makes validation inconclusive and blocks the action\. The check is not an atomic multi\-owner snapshot or a transaction spanning the later external service call; Section[6](https://arxiv.org/html/2609.03340#S6)discusses those boundaries\.

## 4Dependency\-ScopedPlanFence

The three requirements above map directly toPlanFence\. Writers first record exact derivation, tool wrappers declare the action’s dependency scope, and the executor compares the resulting frontier with owner heads immediately before execution\. A mismatch causes one refresh and replan before the action is revalidated or blocked\.

### 4\.1Recording action\-relevant lineage

Application code attaches exact parent IDs whenever it writes a derived public record\. Thus a requirement revision cites its previous version, and a role decision cites the requirement visible when the decision was produced\. Tool wrappers separately declareD⁡\(a\)D\(a\)\. This dependency contract is part of the trusted computing base: a wrapper must capture dynamic public reads or conservatively declare a broader set\.

At validation, ownero⁡\(x\)o\(x\)returns the current immutable record IDH⁡\(x\)H\(x\)for each declared key\. Exact message and conflict checks are implementation details given in Appendix[A](https://arxiv.org/html/2609.03340#A1)\. Metadata normally moves without record content; the executor fetches and verifies changed content only after it observes a mismatch\.

### 4\.2Dependency\-scoped action gate

Algorithm[1](https://arxiv.org/html/2609.03340#algorithm1)implements the gate\. The executor first traverses local exact parents and rejects an incomplete lineage\. It then querieso⁡\(x\)o\(x\)for everyx∈D⁡\(a\)x\\in D\(a\)concurrently\. Matching frontiers authorize the action; a mismatch returns verified current records for one fresh plan\. The caller invokes the gate once more withreplannedset, so a second change or any incomplete response blocks instead of creating an unbounded replan loop\.

Algorithm 1Dependency\-scoped validation at a protected action\.Input:actionaa, rootsL⁡\(a\)L\(a\), dependenciesD⁡\(a\)D\(a\), flagreplanned

1Traverse exact parents from

L⁡\(a\)L\(a\)to the semantic\-key boundaries in

D⁡\(a\)D\(a\)
2if*a derived parent, dependency boundary, or owner mapping is missing*then

3returnblocked

4

F←F\\leftarrowboundary record IDs observed in the local lineage

5

H⁡\(x\)←H\(x\)\\leftarrowconcurrently query

o⁡\(x\)o\(x\)for each

x∈D⁡\(a\)x\\in D\(a\)
6if*an owner response is unavailable, malformed, conflicting, or identifies the wrong key*then

7returnblocked

8Fetch and verify exact records for keys with

H⁡\(x\)≠F⁡\(x\)H\(x\)\\neq F\(x\)
9if*F≠HF\\neq Hor the roots do not derive fromFF*then

10if*replanned*then

11returnblocked

12returnreplan\-required with

HH
13returnauthorized at the logged validation point

### 4\.3Coordination cost and policy boundary

LetRRbe dirty owner updates between protected actions andd=\|D⁡\(a\)\|d=\|D\(a\)\|\. Per\-update metadata sync distributesO⁡\(R​N\)O\(RN\)owner heads early and compares the plan’s parents with the installed heads\. Centralized lineage serializesO⁡\(R\)O\(R\)commits and later reads\. At action time, batched all\-key validation checks and serializes\|𝒳\|\|\\mathcal\{X\}\|heads, whereasPlanFencechecks only theddkeys inD⁡\(a\)D\(a\)\.

These are head\-item counts rather than TCP request counts: either action\-time policy can batch multiple heads into one request per contacted owner\.PlanFencefetches content only for dependencies whose IDs changed\. The comparison does not makePlanFenceuniversally cheaper\. WhenRRis small and links are fast, proactive synchronization removes action\-time owner round trips; as churn or irrelevant shared state grows, its broader coordination becomes more costly\. The experiments measure this crossover rather than inferring it from the asymptotic terms\.

## 5Experiments

### 5\.1Experimental Design

Together with the transport microbenchmark in Figure[2](https://arxiv.org/html/2609.03340#S3.F2), we use live five\-agent workflows and controlled replay\. The live workflows test stale\-plan execution and repair; controlled replay compares safety, stall, and traffic under identical schedules\.

Live and controlled workflows\.Five Qwen3\.5 agents solve reservation, fulfillment, and deployment workflows through separate processes and agent\-local public state\. These runs test whether a model\-generated plan can remain stale after the executor reads a revised requirement\. A separate post\-hoc audit found the defining pattern in 15/30 exploratory workflows: the executor read the revision but acted from a plan tied to the initial requirement\. Those plans did not yet attach immutable memory records as exact parents, and we do not use this exploratory count to estimate natural failure incidence\. Appendix[A\.4](https://arxiv.org/html/2609.03340#A1.SS4)reports the full exploratory audit\. The matched intervention below supplies the causal comparison\.

For policy comparison, controlled replay deliberately fixes the decisions in 30 public workflow templates while executing the same memory, transport, and validation paths through 3\-8 agent\-local copies\. This design attributes invalid actions, waiting time, and traffic to the memory policy rather than model\-output variation\. The live workflows ground the basic five\-agent, one\-revision case\. Higher update rates, wider dependency sets, larger keyspaces, and deeper parent chains are controlled stress tests\.

Baselines\.We use the same policy names in every table and figure\.*Local replica*acts from installed state, while*Owner\-head freshness*reads the current dependency without proving that the plan descends from it\. Both deliberately omit lineage\. The safe policies bind a plan to exact input IDs and replan once after a mismatch\.*Centralized lineage*uses one shared service;*Metadata sync,K=1K=1*announces every dirty owner head;*Per\-key all\-key validation*queries each shared key separately;*Batched all\-key validation*returns all shared\-key heads in one request per owner; andPlanFencequeries onlyD⁡\(a\)D\(a\)\. We additionally test*Majority\-replica validation*and*All\-replica dependency validation*as strong distributed controls\. Metadata sync withK\>1K\>1is a safety\-cost sensitivity, not a safe headline competitor, because it may compare against an obsolete announced head\. In conceptual terms, eager invalidation after every owner update is Metadata sync \(K=1K=1\), one strong shared memory service is Centralized lineage, a global epoch is a broad all\-key check, and quorum\-style reads are represented by the replica controls\.

Workloads and comparisons\.Each episode forms a plan, changes public requirements, and attempts a protected action under every policy\. The primary setting uses eight semantic keys, five agents, 64 work units, one action dependency, and nominal update targetsρ∈\{0\.25,1,4,16\}\\rho\\in\\\{0\.25,1,4,16\\\}\. AtH=64H=64, the schedules realize 0\.25, 1\.0,42/11≈3\.8242/11\\approx 3\.82, and 14 updates per protected action\. We test loopback and fixed AT&T, T\-Mobile, and Verizon LTE traces\.

The keyspace study varies 8\-128 shared keys at five agents, one dependency,H=64H=64, andρ=4\\rho=4\. Its primary reactive baseline batches all\-key heads into one request per owner; per\-key requests expose an implementation sensitivity\. Team size, dependency count, episode length, and quorum provide additional cost checks\. Symmetric artifact consumption is retained only as a safety and payload\-path control\. Appendix[B](https://arxiv.org/html/2609.03340#A2)reports the complete grids and secondary sensitivity controls\.

Metrics and analysis\.The safety endpoint counts issued actions whose plan does not reach every current declared input\. We report raw safety, availability, and task\-completion counts\.*Coordination stall*is time waiting for synchronization or validation, and distributed traffic includes inter\-replica and central\-service bytes\. Cost comparisons pair identical schedules and bootstrap over workflow families; differences below 10% are treated as practical ties\. Appendix[A\.1](https://arxiv.org/html/2609.03340#A1.SS1)gives the zero\-event bounds, resampling procedure, completion criterion, and timeout treatment\.

Table 1:Exact plan binding prevents stale\-plan actions; at high churn,PlanFencehas the lowest stall and traffic among safe policies\.Results use eight\-key compact state, the pinned AT&T trace, and the high\-update workload \(42 updates and 11 protected actions per episode\)\. Every row opens a new TCP connection per RPC\. Bold and underlined costs mark the best and second\-best values among zero\-invalid, fully available policies; delayed synchronization is shown only as a safety\-cost sensitivity\.Table[1](https://arxiv.org/html/2609.03340#S5.T1)provides the safety and cost overview\. Its first invalid\-action and availability columns establish the safety boundary: a current record is insufficient unless the pending plan is bound to that exact record\. Among policies with zero invalid actions and full availability, the cost columns then expose the systems choice\. Figures[3](https://arxiv.org/html/2609.03340#S5.F3)through[5](https://arxiv.org/html/2609.03340#S5.F5)show why no policy minimizes both coordination stall and traffic in every measured regime\.

### 5\.2RQ1: Can Latest State Still Lead to an Outdated Plan?

Fresh owner state does not invalidate an obsolete derivation; exact lineage does\.Table[1](https://arxiv.org/html/2609.03340#S5.T1)stages the race from Figure[1](https://arxiv.org/html/2609.03340#S1.F1)\. Local replicas and owner\-head checks without lineage both issue 330/330 actions from obsolete plans\. Every strong policy that binds the plan to its inputs instead issues 330/330 lineage\-valid actions\. Appendix[A\.6](https://arxiv.org/html/2609.03340#A1.SS6)extends this check across the aligned policy audit: among 32,700 scheduled actions, it finds no invalid action for any method that enforces exact lineage\. The sharp counts are protocol outcomes rather than model\-accuracy estimates because every staged schedule deliberately places a revision between planning and action\.

Live system\.Five Qwen3\.5 agents run in separate role processes across reservation, fulfillment, and deployment workflows, with ten seeds per family\.Stale\-plan intervention\.Role\-local state→\\rightarrowmodel planp⁡\(r3\)p\(r\_\{3\}\)→\\rightarrowowner revisionr4r\_\{4\}→\\rightarrowprotected tool action\.MethodMemoryTasksuccessInvalid primary/ scheduledSuccessfulreplansRedundantauditor actionsOwner\-head freshnessReplicated0/3030/30–0Centralized lineageShared30/300/3030/304PlanFence\(ours\)Replicated30/300/3030/3010Table 2:Exact\-lineage validation repairs model\-generated stale plans before the protected action\.Centralized lineage andPlanFenceeach replan successfully in all 30 interactive five\-agent workflows\. Redundant auditor actions are retained as model\-side variation and are not synchronization\-cost measurements\.The stale\-plan failure persists when model\-generated plans drive tool use\. Table[2](https://arxiv.org/html/2609.03340#S5.T2)follows five Qwen3\.5 agents through reservation, fulfillment, and deployment workflows from role\-local public state, inserting one requirement revision after planning but before the protected action\. Reading the newest owner record without checking the plan issues an obsolete primary action in all 30 tasks\. Centralized lineage andPlanFenceinstead detect the changed input, invoke one fresh planner call, and complete all 30 tasks without an invalid primary action\. Their auditors unnecessarily repeat 4 and 10 already\-valid actions, respectively; we retain these model\-side false positives and do not use the study for synchronization\-cost comparison\.*PlanFencetherefore matches centralized\-lineage safety and completion in an interactive five\-agent system while preserving distributed, owner\-managed memory\.*

### 5\.3RQ2: Synchronize Every Update or Validate Before Action?

Per\-update synchronization has lower stall in the measured low\-churn regime, whilePlanFencehas lower stall than the safe proactive alternatives atρ≥4\\rho\\geq 4\.Figure[3](https://arxiv.org/html/2609.03340#S5.F3)maps this boundary across loopback and three cellular traces\. Each cell comparesPlanFencewith the faster of per\-update metadata sync and centralized lineage\. The proactive choice has a lower point estimate in seven of the eight cells withρ≤1\\rho\\leq 1, while both loopback comparisons are practical ties under our 10% threshold\.PlanFenceleads in all eight cells withρ≥4\\rho\\geq 4, by 1\.5×\\timesto 7\.1×\\timesrelative to the next\-lowest safe policy\.

![Refer to caption](https://arxiv.org/html/2609.03340v1/causal_sync_policy_boundary.png)Figure 3:Metadata sync has lower stall at low churn;PlanFencehas lower stall at high churn\.Each cell comparesPlanFencewith the lower\-stall safe choice between metadata sync \(K=1K=1\) and centralized lineage\. The in\-cell value is the runner\-up/winner stall ratio\. Gray marks differences below the declared 10% practical threshold; teal denotesPlanFenceand blue denotes metadata sync\. The legend defines the in\-cell abbreviations\. Centralized lineage is included in every cell but never has the lowest stall\.Figure 4:On the AT&T trace, the safe\-policy boundary lies between the measured nominal targetsρ=1\\rho=1andρ=4\\rho=4\.Metadata sync \(K=1K=1\) has lower stall atρ=0\.25\\rho=0\.25andρ=1\\rho=1;PlanFencehas lower stall atρ=4\\rho=4andρ=16\\rho=16\. Numbers inside the metadata\-sync markers denoteKK; values withK\>1K\>1reduce stall only by issuing invalid actions\. All measurements use compact state\.Delaying metadata synchronization trades safety for lower stall\. Figure[4](https://arxiv.org/html/2609.03340#S5.F4)makes this tradeoff explicit on the AT&T trace: increasingKKreduces proactive coordination but leaves the announced head obsolete between barriers and admits more lineage violations\. Table[4](https://arxiv.org/html/2609.03340#A2.T4)reports the underlying counts and costs\. Tables[5](https://arxiv.org/html/2609.03340#A2.T5)and[7](https://arxiv.org/html/2609.03340#A2.T7)vary team size and episode length\. Across theseρ=4\\rho=4sensitivity checks,PlanFencehas lower stall than centralized lineage and metadata sync \(K=1K=1\) forN=3,5,8N=3,5,8andH=16,64,256H=16,64,256, with 8\.0\-8\.2 KiB/action of traffic\. The secondary endpoints use three templates and serve as sensitivity checks rather than standalone population estimates\.*The measured crossover marks a shift from paying coordination after every update to paying it when an action validates its dependencies\.*

### 5\.4RQ3: Check Action\-Relevant State or All Shared State?

With equal post\-replan validation, dependency scope lowers both stall and traffic across the measured keyspaces\.Table[1](https://arxiv.org/html/2609.03340#S5.T1)first compares centralized lineage, metadata sync \(K=1K=1\), andPlanFencein the primary eight\-key compact\-state setting on the AT&T trace at nominalρ=4\\rho=4\. All three complete 330/330 valid actions, whilePlanFenceuses 230\.8 ms and 8\.1 KiB per action, compared with 508\.6 ms/15\.6 KiB for centralized lineage and 403\.4 ms/23\.5 KiB for metadata sync; the ordering also holds on the other traces\. Figure[5](https://arxiv.org/html/2609.03340#S5.F5)next comparesPlanFencewith batched all\-key validation under the same one\-replan, two\-validation path as the shared keyspace grows from 8 to 128 keys\.

The action depends on one key\. Batched all\-key validation checks every shared key in one request per owner, whereasPlanFencequeries only the dependency owner\. Under these matched semantics,PlanFencelowers median stall from 115\.5 to 67\.8 ms/action at eight loopback keys and from 199\.2 to 66\.0 ms/action at 128 keys\. Across three AT&T trace offsets, the corresponding medians are 365\.7 versus 295\.3 ms/action at eight keys and 428\.7 versus 345\.2 ms/action at 128 keys\. Its traffic remains near 8\.1 KiB/action while the all\-key check grows from 16\.4 to 81\.7 KiB/action\.

Figure 5:Dependency scope avoids serializing irrelevant shared\-key heads\.Relative to batched all\-key validation,PlanFencelowers stall and traffic at every measured key count under the same one\-replan, two\-validation rule\. Loopback points aggregate 30 templates\. AT&T points are medians over three independent trace\-offset aggregates; Appendix Table[9](https://arxiv.org/html/2609.03340#A2.T9)reports each offset\.The benefit also depends on how much of the keyspace the action actually uses\. Appendix Table[6](https://arxiv.org/html/2609.03340#A2.T6.fig1)holds\|𝒳\|=8\|\\mathcal\{X\}\|=8fixed and widens the dependency set\.PlanFencelowers stall by 14\.9% and traffic by 50\.6% atd=1d=1\. Atd=2d=2, stall is a practical tie while traffic remains 32\.0% lower\. Atd=8=\|𝒳\|d=8=\|\\mathcal\{X\}\|, the two validation scopes coincide and both stall and traffic are practical ties\. This convergence is the expected boundary of dependency scoping rather than a regime in whichPlanFenceshould dominate\.

Independent trace phases support the same aggregate pattern\. At 128 keys, the pairedPlanFence\-minus\-batched\-all\-key stall interval excludes zero at every AT&T trace offset, and the traffic interval excludes zero in every measured network/keyspace stratum\. At eight keys, one of the three stall intervals crosses zero, so the latency ordering is not pointwise uniform\. Table[8](https://arxiv.org/html/2609.03340#A2.T8)in Appendix[B](https://arxiv.org/html/2609.03340#A2)reports every aggregate, and Table[9](https://arxiv.org/html/2609.03340#A2.T9)reports the independent AT&T trace offsets\.*When both methods enforce the same safety rule,PlanFencepreserves valid completion while avoiding all\-key work that is irrelevant to the pending action\.*

## 6Limitations

Our evaluation is designed to isolate the behavior of the memory policy rather than measure general agent capability\. Controlled replay lets every policy face the same decisions and update schedules, while the live workflows show that a model\-generated plan can become stale and be repaired before execution\. The evidence nevertheless covers only three workflow families, 3\-8 agents, constructed keyspaces, and a small set of historical network traces\. We therefore treat the stress\-test intervals as descriptive and do not infer a general improvement in task quality from them\.

PlanFence’s safety guarantee also depends on a clear systems boundary\. Owners must be benign, parent links exact, and each tool wrapper responsible for a complete dependency declaration\. The present design does not address Byzantine owners, owner migration, inferred dependencies, semantic merging, or private reasoning that never enters the public lineage\. Moreover, validation is atomic neither across multiple owners nor with the external action itself; applications that require either property need a transaction mechanism that spans the corresponding boundary\. These assumptions determine when the action fence is safe, while engineering choices such as connection reuse, metadata placement, and artifact access can still shift the measured coordination\-cost crossover\.

## 7Conclusion

Stale\-plan execution is a lineage failure: current state can coexist with an obsolete derivation\.PlanFencerecords exact parents, validates declared dependencies, replans once, and fails closed\. Per\-update synchronization has lower stall at low churn;PlanFenceavoids repeated coordination as churn grows\. Against batched all\-key validation, it lowers measured stall and traffic when actions depend on a sparse subset of shared state, and the advantage vanishes as the dependency set reaches the full keyspace\. We claim neither universal dominance nor general task\-quality gains\.

## References

- \[1\]D\. Abadi\(2012\)Consistency tradeoffs in modern distributed database system design: cap is only part of the story\.Computer45\(2\),pp\. 37–42\.Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p4.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px2.p1.1)\.
- \[2\]Anthropic\(2024\)Model context protocol\.Note:modelcontextprotocol\.ioCited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[3\]H\. Attiya, A\. Bar\-Noy, and D\. Dolev\(1995\)Sharing memory robustly in message\-passing systems\.Journal of the ACM42\(1\),pp\. 124–142\.Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p4.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px2.p1.1)\.
- \[4\]P\. Bailis, S\. Venkataraman, M\. J\. Franklin, J\. M\. Hellerstein, and I\. Stoica\(2012\)Probabilistically bounded staleness for practical partial quorums\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px2.p1.1)\.
- \[5\]P\. Buneman, S\. Khanna, and T\. Wang\-Chiew\(2001\)Why and where: a characterization of data provenance\.InInternational conference on database theory,pp\. 316–330\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px1.p1.1)\.
- \[6\]P\. Chhikara, D\. Khant, S\. Aryan, T\. Singh, and D\. Yadav\(2025\)Mem0: building production\-ready ai agents with scalable long\-term memory\.arXiv preprint arXiv:2504\.19413\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[7\]A\. Demers, D\. Greene, C\. Hauser, W\. Irish, J\. Larson, S\. Shenker, H\. Sturgis, D\. Swinehart, and D\. Terry\(1987\)Epidemic algorithms for replicated database maintenance\.InProceedings of the sixth annual ACM Symposium on Principles of distributed computing,pp\. 1–12\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px2.p1.1)\.
- \[8\]Y\. Du, S\. Li, A\. Torralba, J\. B\. Tenenbaum, and I\. Mordatch\(2024\)Improving factuality and reasoning in language models through multiagent debate\.InInternational Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[9\]S\. Gilbert and N\. Lynch\(2002\)Brewer’s conjecture and the feasibility of consistent, available, partition\-tolerant web services\.ACM SIGACT News33\(2\),pp\. 51–59\.Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p4.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px2.p1.1)\.
- \[10\]Google\(2025\)Agent2Agent \(A2A\) protocol\.Note:github\.com/a2aproject/A2ACited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[11\]S\. Hong, X\. Zheng, J\. Chen, Y\. Cheng, J\. Wang, C\. Zhang, Z\. Wang, S\. K\. S\. Yau, Z\. Lin, L\. Zhou,et al\.\(2024\)MetaGPT: meta programming for a multi\-agent collaborative framework\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p1.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[12\]T\. Kraska, M\. Hentschel, G\. Alonso, and D\. Kossmann\(2009\)Consistency rationing in the cloud: pay only when it matters\.InProceedings of the VLDB Endowment \(VLDB\),Vol\.2,pp\. 253–264\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px2.p1.1)\.
- \[13\]H\. Kung and J\. T\. Robinson\(1981\)On optimistic methods for concurrency control\.ACM Transactions on Database Systems \(TODS\)6\(2\),pp\. 213–226\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px1.p1.1)\.
- \[14\]C\. Li, D\. Porto, A\. Clement, J\. Gehrke, N\. Preguiça, and R\. Rodrigues\(2012\)Making\{\\\{geo\-replicated\}\\\}systems fast as possible, consistent when necessary\.In10th USENIX Symposium on Operating Systems Design and Implementation \(OSDI 12\),pp\. 265–278\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px2.p1.1)\.
- \[15\]G\. Li, H\. A\. A\. K\. Hammoud, H\. Itani, D\. Khizbullin, and B\. Ghanem\(2023\)CAMEL: communicative agents for “mind” exploration of large language model society\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p1.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[16\]C\. Packer, S\. Wooders, K\. Lin, V\. Fang, S\. G\. Patil, I\. Stoica, and J\. E\. Gonzalez\(2023\)MemGPT: towards LLMs as operating systems\.arXiv preprint arXiv:2310\.08561\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[17\]S\. Pal, F\. Y\. Wang, and M\. J\. Buehler\(2026\)SwarmWorld: stigmergic technological evolution in societies of language\-model agents\.arXiv preprint arXiv:2608\.26081\.Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p2.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[18\]C\. Qian, W\. Liu, H\. Liu, N\. Chen, Y\. Dang, J\. Li, C\. Yang, W\. Chen, Y\. Su, X\. Cong,et al\.\(2024\)Communicative agents for software development\.InAnnual Meeting of the Association for Computational Linguistics \(ACL\),Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p1.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[19\]A\. Rezazadeh, Z\. Li, A\. Lou, Y\. Zhao, W\. Wei, and Y\. Bao\(2025\)Collaborative memory: multi\-user memory sharing in LLM agents with dynamic access control\.arXiv:2505\.18279\.Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p1.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[20\]M\. Shapiro, N\. Preguiça, C\. Baquero, and M\. Zawirski\(2011\)Conflict\-free replicated data types\.InSymposium on Self\-Stabilizing Systems \(SSS\),pp\. 386–400\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px2.p1.1)\.
- \[21\]N\. Shinn, F\. Cassano, A\. Gopinath, K\. Narasimhan, and S\. Yao\(2023\)Reflexion: language agents with verbal reinforcement learning\.InAdvances in neural information processing systems,Vol\.36,pp\. 8634–8652\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[22\]D\. B\. Terry, V\. Prabhakaran, R\. Kotla, M\. Balakrishnan, M\. K\. Aguilera, and H\. Abu\-Libdeh\(2013\)Consistency\-based service level agreements for cloud storage\.InProceedings of the twenty\-fourth ACM symposium on operating systems principles,pp\. 309–324\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px2.p1.1)\.
- \[23\]G\. Wang, Y\. Xie, Y\. Jiang, A\. Mandlekar, C\. Xiao, Y\. Zhu, L\. Fan, and A\. Anandkumar\(2023\)Voyager: an open\-ended embodied agent with large language models\.arXiv preprint arXiv:2305\.16291\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[24\]Y\. Wang and X\. Chen\(2025\)MIRIX: multi\-agent memory system for LLM\-based agents\.arXiv:2507\.07957\.Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p1.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[25\]Q\. Wu, G\. Bansal, J\. Zhang, Y\. Wu, S\. Zhang, E\. Zhu, B\. Li, L\. Jiang, X\. Zhang, and C\. Wang\(2023\)AutoGen: enabling next\-gen LLM applications via multi\-agent conversation framework\.arXiv preprint arXiv:2308\.08155\.Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p1.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[26\]W\. Xu, Z\. Liang, K\. Mei, H\. Gao, J\. Tan, and Y\. Zhang\(2025\)A\-MEM: agentic memory for LLM agents\.arXiv preprint arXiv:2502\.12110\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[27\]Z\. Yu, N\. Yu, H\. Zhang, W\. Ni, M\. Yin, J\. Yang, Y\. Zhao, and J\. Zhao\(2026\)Multi\-agent memory from a computer architecture perspective: visions and challenges ahead\.arXiv:2603\.10062\.Cited by:[§1](https://arxiv.org/html/2609.03340#S1.p1.1),[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[28\]G\. Zhanget al\.\(2025\)Cut the crap: an economical communication pipeline for LLM\-based multi\-agent systems\.ICLR \(arXiv:2410\.02506\)\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[29\]G\. Zhanget al\.\(2025\)Multi\-agent architecture search via agentic supernet\.ICML \(arXiv:2502\.04180\)\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.
- \[30\]M\. Zhugeet al\.\(2024\)GPTSwarm: language agents as optimizable graphs\.ICML \(arXiv:2402\.16823\)\.Cited by:[§2](https://arxiv.org/html/2609.03340#S2.SS0.SSS0.Px3.p1.1)\.

## Appendix AImplementation Details

Table[3](https://arxiv.org/html/2609.03340#A1.T3)lists the settings needed to reproduce the runtime behavior\. Five agent processes participate\. Replicated methods use one SQLite memory process per agent, while central lineage uses one shared SQLite memory process\. All communication uses authenticated TCP\. Public records are immutable JSON objects in durable SQLite stores\. Paired policies receive the same initial records and schedules, and network impairments begin only after setup\. We rerun only trials that terminate before any policy decision because of infrastructure failure\. Policy\-induced blocks, failures, and timeouts remain in all reported denominators\.

Each stored public version carries its semantic key, immutable record ID, authoritative owner, monotone owner sequence, exact parent IDs, record type, content size, and public content or content address\. An owner accepts a head update only when the writer identity matches the declared owner and the sequence increases; duplicate owner sequences are conflicts\. Head announcements send the metadata envelope, while consumers fetch content only after discovering that their local version is obsolete\.

Table 3:Implementation and harness configuration\.### A\.1Metrics and statistical analysis

Binary endpoints are reported as raw counts\. For zero observed invalid actions, the one\-sided 95% exact\-binomial upper bounds are 0\.90% for 0/330, 9\.5% for 0/30, and 0\.023% for 0/13,200\. These bounds describe empirical implementation coverage; the protocol invariant remains conditional on the assumptions in Section[4](https://arxiv.org/html/2609.03340#S4)\. Cost comparisons pair identical schedules and use 2,000 bootstrap draws that resample the three workflow families as clusters\. We regard a 10% reduction in median stall or traffic as practically meaningful when safety does not weaken and availability falls by no more than five percentage points\. With three families, the intervals describe stability across those families rather than population\-wide uncertainty\. In Figure[2](https://arxiv.org/html/2609.03340#S3.F2), the 117\.42 ms line is an analytical reference rather than an end\-to\-end target; elapsed durations from 2 s transport timeouts remain in the latency summaries\.

### A\.2Controlled live prompting and tool grounding

Each role receives the same short system instruction with its role and workflow family substituted\. The user content is a stable JSON object assembled from only the role’s local public state and prior public handoffs\. The tool schema then enumerates every permitted identifier, action name, and argument object\.

Controlled live\-agent promptSystem\.You are<WORK\_UNIT\>in a controlled<FAMILY\>workflow\. Use only supplied evidence\. Call exactly one supplied tool\. Do not invent IDs or hidden state\. The tool schema enumerates the complete allowed IDs and actions for this decision\.User object\.Local requirement and its application\-level request ID; an opaque digest of the local requirement revision; up to five locally eligible catalog candidates; prior public handoffs; and, for the auditor, the externally visible action outcome\.Grounded tool\.Exactly one function call is required\. Candidate IDs, requirement revision, action name, and complete action arguments are finite enumerations constructed from the local query\. Additional fields are rejected\.

One public correction is allowed after a schema violation\. The correction contains the rejection reason and required tool name but no hidden answer\. A second violation fails the attempt\. Model\-facing handoffs contain role content only; raw memory\-record IDs, owner IDs, and evaluator fields remain inside the workflow adapter\.

### A\.3Protected\-action and replan harness

One\-replan protected\-action path1\. Validate\.Query authoritative heads for the declared dependencies and verify that the proposed action root derives from the planned records\.2\. Refresh\.If a dependency changed, fetch and verify its exact public record\. Malformed or unavailable state blocks the action\.3\. Replan once\.Invoke the same role with isolated conversational history and a JSON object containingreplan\_required, the old action, fresh requirement, fresh eligible candidates, and public handoffs\.4\. Revalidate and propagate\.Validate the new action root, execute one primary action, and pass the fresh root and validated dependency to the downstream auditor before its first model call\. A second version change blocks\.

The replay uses the same validation code but replaces the model replan with a recorded fresh public decision\. It therefore measures the memory mechanism and network path without attributing fixed decisions to new model calls\.

### A\.4Exploratory live\-workflow audit

Before examining stale plans, we verified that the model and tools could solve the workflow with centralized state\. All 30 paired tasks completed, and all 480 role decisions satisfied their public tool schemas\.

The prespecified audit then asked whether the executor itself read an obsolete requirement\. Only 3/30 runs did, below its prespecified threshold of 15\. A separate post\-hoc analysis revealed a different failure: 28/30 generated plans cited the initial application requirement, and in 15 cases the executor read the revision but still issued the invalid action from that stale plan\. These cases span deployment, fulfillment, and reservation with counts 6, 2, and 7\. The model produced 240 accepted role decisions from 241 responses, with no unrecovered schema, workflow\-contract, or infrastructure failure\.

Those plan records stored the application requirement ID in their public payload but did not yet attach the immutable memory record as a parent\. The audit therefore shows that generated plans can remain stale; the replay and the matched live study provide the exact\-lineage comparison\.

### A\.5Matched controlled\-live check

The matched study crosses three workflow families, ten evaluation seeds, and three memory methods, for 90 attempts\. Each task forms a plan over the initial requirement and then receives one owner revision before execution\. Owner\-head freshness exposes the new record without checking whether the plan used it\. Centralized lineage andPlanFenceinstead validate the plan, fetch the revised input, invoke one isolated planner call, and validate again before acting\.

Owner\-head freshness issues the stale action and fails all 30 tasks\. Centralized lineage andPlanFenceeach complete 30/30 tasks with no invalid action and one successful replan per task\. Their auditors unnecessarily repeat 4 and 10 valid actions, respectively\. This model\-side variation prevents a live cost comparison, but it does not alter the safety outcome because every protected primary action was already valid\.

All 90 attempts complete, and the model produces 780 accepted role decisions from 784 responses\. Four initial schema errors are corrected by the one allowed public retry; none remains unrecovered\. Each paired centralized\-lineage andPlanFencerun follows the same workflow steps, and no infrastructure or tool\-contract failure occurs\.

### A\.6Evaluation coverage

The 30\-template corpus includes 241 retained live latency samples, while the aligned policy grid schedules 32,700 actions: every exact\-lineage method remains safe and available, and stale or delayed\-sync controls account for all 4,143 invalid actions\. The matched keyspace study completes 13,200/13,200 actions and supplies the scope\-cost comparison\. The artifact control completes 15,360/15,360 actions with zero lineage violations and two verified fetches per policy and action; because it uses a different action path, it supports payload\-path safety but not comparative stall\.

## Appendix BControlled\-replay ablations

The following studies ask whether the main boundary survives changes in synchronization cadence, team size, dependency count, and episode length\. “Valid” means an issued action whose plan reaches every current declared input; a blocked action never enters that numerator\. Unless noted otherwise, the tables use compact records, the AT&T trace, andρ=4\\rho=4\.

Table 4:Synchronization cadence across nominal update targets\. Waiting more than one work unit reduces proactive cost by allowing invalid stale\-plan actions\.Table 5:Team\-size sensitivity with one dependency per action\. The high\-update policy ordering remains stable from three to eight agents\.Table 6:Dependency\-scope benefits narrow as the action approaches the full keyspace\.Both methods fetch only changed dependency records concurrently and use the same one\-replan, two\-validation rule over 30 templates\. Atd=1d=1,PlanFencelowers stall and traffic; atd=2d=2, stall is a practical tie while traffic remains lower; atd=8=\|𝒳\|d=8=\|\\mathcal\{X\}\|, both endpoints are practical ties under the 10% threshold\.Table 7:Episode\-length sensitivity for the three primary policies\. The high\-update ordering persists from 16 to 256 work units\.Table 8:Complete aligned semantic\-keyspace comparison\. Loopback rows aggregate 30 templates; AT&T rows aggregate the same templates at three independent trace offsets\. Both methods use exact lineage, one post\-replan validation, and a new TCP connection per RPC\. All 13,200 scheduled actions complete with valid lineage\.Large\-artifact safety control\.Across 960 runs and 15,360 protected actions, every policy fetches and verifies the same changed public artifact twice per action, and every exact\-lineage action remains valid\. Because this control uses a different action path, we use it to verify payload\-path safety but not comparative stall\.

### B\.1Independent AT&T trace phases

Changing the start point within the AT&T trace changes absolute latency but preserves the pointwise ordering\. Table[9](https://arxiv.org/html/2609.03340#A2.T9)reports the independently replayed 0, 5, and 15 second offsets at both keyspace endpoints\. Both exact\-lineage methods complete every action\.PlanFencehas lower median stall and traffic in all six paired aggregates\. The paired stall interval excludes zero in five of the six 30\-template strata; the eight\-key, five\-second interval crosses zero and remains a descriptive comparison\.

Table 9:Independent AT&T trace phases under the aligned comparison\. Both methods fetch a changed record once, replan once, and validate again\. Bold marks the lower cost within each exact offset and keyspace pair\.
### B\.2Learned policy selection does not dominate a transparent rule under OOD shift

Could a learned selector reduce coordination cost without weakening the safety path? We allow it to choose among centralized lineage, metadata sync \(K=1K=1\), andPlanFence, all of which retain deterministic exact\-lineage validation\. Malformed or unavailable selector output falls back toPlanFence\. The transparent reference uses metadata sync whenρ≤1\\rho\\leq 1andPlanFenceotherwise; learned selectors may also choose centralized lineage\.

We derive 1,332 examples from the complete controlled\-replay campaign, each aggregating six workflows from three families\. A policy is*eligible*if it issues no invalid action and completes every scheduled action\. Among eligible policies within 10% of the lowest stall, the target is the policy with the least wire traffic; we call this a*safe near\-optimal*choice\. The split contains 648 training, 144 development, and 180 in\-distribution \(ID\) examples\. Four disjoint 90\-example out\-of\-distribution \(OOD\) blocks hold out, respectively, the Verizon trace, interpolated update rates\{0\.5,2,8\}\\\{0\.5,2,8\\\}, endpoint key counts\{8,128\}\\\{8,128\\\}, and their compound shift\. Selectors see only pre\-action workload dimensions and static trace calibration, never profile identity, workflow text, outcomes, or future trace events\. Neural results use three\-seed ensembles\.

Learned selectors improve ID selection but do not consistently dominate the transparent rule under shift\. Table[10](https://arxiv.org/html/2609.03340#A2.T10)reports 95\.0\-96\.7% safe near\-optimal selection for the learned models on ID examples, compared with 89\.4% for the transparent rule\. Under shift, the tree and tabular networks fall to 84\.4\-94\.2%\. DeBERTa\-v3\-base reaches 96\.1%, but its conservative three\-model batch\-one inference costs 34\.08 ms\. We consider a selector robust only if it is no worse in completion, safe near\-optimal choice, Pareto domination, traffic regret, and p95 stall regret after inference, with at least one strict improvement in every OOD block\. None passes all four blocks: the tabular models pass only the keyspace block, and neither DeBERTa model passes any block after inference cost\. Exact\-lineage safety nevertheless remains deterministic under every selector\.

Safe near\-optimal↑\\uparrow\(%\)p95 stall regret↓\\downarrow\(ms/action\)p95 inference↓\\downarrowAll\-shiftSelectorIDOODIDOOD\(ms/query\)gateTransparent rate rule89\.495\.024\.726\.5–referenceFixedPlanFence72\.268\.6134\.898\.9––Depth\-3 decision tree95\.084\.417\.675\.70\.08noTwo\-layer MLP96\.794\.27\.535\.40\.21noResidual MLP96\.191\.411\.346\.60\.52noDeBERTa\-v3\-base95\.096\.117\.621\.734\.08noDeBERTa\-v3\-large95\.094\.717\.631\.464\.06noTable 10:Appendix\-only selection among policies that retain deterministic lineage safety\. OOD pools four disjoint 90\-example shifts\. Stall regret is measured against the fastest eligible policy; inference is reported separately and included in the blockwise dominance gate\. Ensemble inference is the conservative sum of the three batch\-one p95 measurements\. “No” means the learned selector does not dominate the transparent rule in every OOD block\.

## Appendix CValidation assumptions and component sensitivities

These studies ask which components the guarantee requires: following the full parent chain, replanning after a detected change, declaring every dependency, and blocking when validation cannot finish\. They isolate mechanism behavior rather than network cost or natural error frequency\.

The same lineage traversal used byPlanFenceauthorizes intact chains through depth eight and blocks whenever an intermediate record is missing\. Checking only a direct parent works at depth one but cannot prove deeper chains\. Replanning turns all 3,000 detected races into valid actions; validation without replanning blocks all 3,000\. Reading a fresh requirement without checking its plan, or trusting an arbitrary replica’s head, issues an invalid action in every race\. Table[11](https://arxiv.org/html/2609.03340#A3.T11)reports the raw outcomes\.

Table 11:Full lineage traversal is necessary beyond one parent, and replanning converts detected races from blocked to available\. “Block” is safe but unavailable; it is never counted as a valid issued action\.Figure[6](https://arxiv.org/html/2609.03340#A3.F6)tests the static dependency\-contract assumption over 30 templates and 100 race seeds\. Of four truedependencies, one remains declared while the other three are independentlyomitted\. Unsafe issuance rises from 0% to 37\.4% as the omission probability reaches 50%\. Overdeclaration remains safe but grows owner\-head checks from four to 36 per action\. Under owner outage, missing lineage, malformed owner heads, and a second version change, fail\-closed validation blocks all four cases with no issued action; the corresponding fail\-open ablation issues an invalid action in all four\. These results justify complete contracts and fail\-closed behavior; they do not establish how often either failure occurs in deployed multi\-agent systems\.

Figure 6:Missing dependencies break safety; extra dependencies cost checks\.Left: invalid issued actions under contract omission\. Right: owner\-head checks under safe overdeclaration\.