PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Evan Chen, Shiqiang Wang, Christopher G. Brinton

arXiv:2609.03340v1cs.AI

TL;DR

Distributed LLM-agent teams can read revised shared facts while still executing a plan derived from superseded facts. The paper introduces PLANFENCE, which validates exact action dependencies and permits one replan, achieving safe controlled execution while exposing conditional coordination-cost tradeoffs.

  • Problem

    Fresh executor state does not prove that a pending plan was derived from the currently authorized public records it depends on.

  • Method

    PLANFENCE records exact plan inputs, validates only tool-declared action dependencies with their owners before execution, and replans once or blocks when validation is incomplete.

  • Results

    In 30 controlled live workflows, freshness-only checks issued obsolete actions in every task, whereas PLANFENCE completed all tasks without an invalid action; replay showed conditional stall and traffic boundaries.

  • Takeaways & Limitations

    Proactive synchronization has lower stall at low churn, while PLANFENCE avoids repeated unrelated-state coordination as churn and shared-keyspace size grow.

  • Takeaways & Limitations

    The evidence covers three workflow families, 3–8 agents, constructed keyspaces, and a small set of historical network traces, so it does not establish general task-quality gains.

Abstract

from arXiv · show

Distributed LLM-agent teams can read the latest shared facts and still act on an obsolete plan. A planner may derive an action from requirement $r_3$, another agent may commit $r_4$, and an executor may receive $r_4$ without replacing the plan derived from $r_3$. We call this \emph{stale-plan execution}: state freshness does not establish that the plan authorizing an action remains valid. We introduce PlanFence, 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, whereas PlanFence completes all tasks without an invalid action. Controlled replay reveals two conditional boundaries: proactive synchronization yields lower coordination stall at low churn, while PlanFence avoids 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.

1 Introduction

Distributed LLM-agent systems can separate shared-state updates from the plans that authorize external actions, allowing fresh facts to coexist with stale derivations. PLANFENCE addresses this by validating exact action dependencies, while experiments compare its safety and coordination costs with broader synchronization policies.

  • Motivation: Stale-plan execution occurs when an executor receives revised requirement r4 but still uses plan p(r3) derived from r3.State freshness does not establish that the pending plan remains authorized.
  • Motivation: Strong public-state coordination is safe but may coordinate unrelated records, creating a tradeoff between broad early synchronization and narrow action-time validation.A reservation depends on its requirement, not an unrelated catalog record or another workflow’s state.
  • Our Approach: PLANFENCE binds plans to exact public inputs, validates tool-declared dependencies, and permits one replan before authorizing or blocking an action.The protocol separates lineage validity from the mechanism used to establish it.
  • Evaluation: 30 controlled live workflows show freshness-only owner-head checks issuing obsolete actions in every task, while PLANFENCE completes all tasks without an invalid action.The workflows include a post-plan revision that tests whether revised state replaces the stale plan.
  • Evaluation: At low update rates, proactive synchronization has lower coordination stall; as updates grow, PLANFENCE avoids repeated unrelated-state coordination and lowers stall and traffic against batched all-key validation.The comparison covers tested 8–128 key loopback and AT&T settings.

2 Related Work

PLANFENCE connects provenance and consistency ideas to a different boundary: validating the public inputs of a persistent generated plan before an external action. It complements distributed consistency mechanisms and agent-memory research by specifying which versions must still authorize that action.

  • Provenance and validation: PLANFENCE adapts provenance and optimistic-concurrency ideas by recording a plan’s public inputs and validating them before an external action.Its boundary is action authorization rather than database transaction commit.
  • Distributed consistency: PLANFENCE does not introduce a new consistency model; it specifies which record versions must still authorize a pending action.It can use proactive propagation or action-time owner queries to establish those versions.
  • LLM-agent coordination and memory: Where prior agent-memory work emphasizes what agents communicate, retrieve, or retain, PLANFENCE addresses whether a derived plan remains authorized after shared-state changes.Persistent-world systems make durable agent-authored artifacts and executable descent a related setting.

3 Motivation and Problem Formulation

The paper frames stale-plan prevention as a versioned-lineage problem: an action must be checked against the current owner-authorized versions of the public records that can affect it. This yields a scoped validity condition and explicit assumptions for when validation can authorize execution.

  • 3 Motivation and Problem Formulation: Strong coordination keeps public state current, but paying for synchronization after every dirty update can accumulate delay as payload size, delay, or loss increases.Figure 2 measures one authenticated TCP synchronization rather than complete memory policies.
  • 3 Motivation and Problem Formulation: An executor needs evidence of the plan’s producing versions, the action-relevant public items, and the versions currently authorized by their owners.The required evidence is scoped to the pending action rather than the entire memory system.
  • 3.1 Public state has versions: Private scratchpads, prompts, and hidden reasoning are outside the public-record lineage model.Each agent may still hold local copies of the team’s public state.
  • 3.1 Public state has versions: A semantic key identifies one logical public item across revisions, while immutable record IDs identify versions and derived records retain the exact IDs used to produce them.The authoritative owner reports the currently authorized head for each key.
  • 3.1 Public state has versions: After r4 replaces r3, owner head id4 differs from plan p3’s parent id3 even though installing r4 changes only the executor’s local state.The derivation recorded by p3 remains unchanged.
  • 3.2 What evidence must authorize an action?: An action is lineage-valid exactly when its plan frontier F_a(x) equals the authoritative head H(x) for every declared dependency x in D(a).Equation (1) formalizes equality between plan-used versions and currently authorized versions.
  • 3.3 Why each condition is necessary: Reading the latest local state is insufficient because it cannot show which version produced a cached plan; replanning over r4 changes the frontier from id3 to id4.Action-relevant changes outside D(a) do not invalidate the action, whereas choosing D(a) = X recovers all-key validation.
  • 3.3 Why each condition is necessary: The guarantee assumes exact binding, action-time validation, benign authoritative owners, authenticated transport, immutable parents, and a complete tool-declared dependency set.Missing lineage, unavailable or malformed owner responses, or incomplete declarations make validation inconclusive and block the action.

4 Dependency-Scoped PLANFENCE

PLANFENCE implements an action-boundary gate that traces exact plan parents to declared dependencies, checks their authoritative heads, and permits only one verified replan. Its dependency scope reduces coordination relative to broader validation as irrelevant shared state or update churn grows.

  • Protocol: PLANFENCE records exact parent IDs, requires tool wrappers to declare action dependencies, and compares the resulting frontier with owner heads immediately before execution.A mismatch triggers one refresh and replan before revalidation or blocking.
  • Protocol: At validation, owners return current immutable record IDs; changed content is fetched and verified only after a dependency mismatch.Metadata normally moves without record content.
  • Protocol: The gate rejects incomplete lineage, queries every declared dependency concurrently, authorizes matching frontiers, and blocks after a second change or incomplete response.The one-replan limit prevents an unbounded replan loop.
  • Cost scope: At action time, PLANFENCE checks d keys in D(a), whereas batched all-key validation checks all shared-key heads and per-update synchronization distributes O(RN) owner heads early.Here R is dirty owner updates between protected actions.
  • Cost scope: Dependency validation can batch multiple heads into one request per contacted owner and fetch content only for dependencies whose IDs changed.The head-item counts are not TCP request counts.
  • Algorithm: The algorithm takes action a, roots L(a), dependencies D(a), and a replanned flag as inputs before traversing exact parents to dependency boundaries.It checks missing derived parents, dependency boundaries, and owner mappings before proceeding.
  • Algorithm: Owner responses that are unavailable, malformed, conflicting, or keyed incorrectly prevent authorization, while changed records are fetched and verified against the frontier.The gate returns an authorized result only when the frontier matches the current heads and roots derive from them.
  • Cost boundary: When update churn or irrelevant shared state grows, PLANFENCE avoids repeated coordination, but proactive synchronization has lower stall when churn is small.The experiments measure this crossover rather than claiming universal cost dominance.

5 Experiments

The experiments evaluate stale-plan safety and coordination cost under live workflows and controlled replay. They show that exact lineage prevents invalid actions, while the lower-cost safe policy depends on update churn and dependency scope.

  • Experimental design: 30 controlled live workflows tested five-agent reservation, fulfillment, and deployment tasks with one requirement revision inserted after planning.Controlled replay fixed decisions in 30 public workflow templates to attribute invalid actions, waiting time, and traffic to the memory policy rather than model-output variation.
  • Safety results: 330/330 actions from obsolete plans occurred under local replicas and owner-head freshness checks, while exact-lineage policies issued 330/330 lineage-valid actions.The staged schedules deliberately placed a revision between planning and action, so these are protocol outcomes rather than model-accuracy estimates.
  • Safety results: In all 30 interactive workflows, centralized lineage and PLANFENCE detected changed inputs, replanned successfully, and completed without an invalid primary action.The live workflows used five Qwen3.5 agents; redundant auditor actions were retained as model-side variation rather than synchronization-cost measurements.
  • Coordination stall: At low churn, proactive metadata synchronization generally has lower stall, whereas PLANFENCE leads in all eight measured cells with ρ ≥4 by 1.5× to 7.1× versus the next-lowest safe policy.The proactive choice has a lower point estimate in seven of eight cells with ρ ≤1, while both loopback comparisons are practical ties under the 10% threshold.
  • Dependency scope: Under matched validation semantics, PLANFENCE lowers stall and traffic as shared keyspaces grow by validating only the action dependency.At 128 keys, loopback stall is 67.8 versus 199.2 ms/action and traffic remains near 8.1 KiB/action versus 81.7 KiB/action for batched all-key validation.
  • Dependency scope: Dependency scoping converges with all-key validation when the action depends on the entire keyspace.With |X| = 8 and d = 8, stall and traffic are practical ties; at d = 1, PLANFENCE lowers stall by 14.9% and traffic by 50.6%.

6 Limitations

The evaluation isolates memory-policy behavior rather than general agent capability and covers a limited set of workflows, agents, keyspaces, and network traces. PlanFence’s safety guarantee also depends on benign owners, exact parent links, and complete dependency declarations.

  • The evaluation measures memory-policy behavior, not general agent capability.Evidence covers three workflow families, 3–8 agents, constructed keyspaces, and a small set of historical network traces.
  • The reported stress-test intervals describe these tested settings rather than population-wide uncertainty or general task-quality improvement.The authors explicitly avoid inferring general task-quality gains from the stress tests.
  • PlanFence’s guarantee assumes benign owners, exact parent links, and complete dependency declarations.The protocol does not address Byzantine owners, owner migration, inferred dependencies, semantic merging, or private reasoning absent from public lineage.
  • Validation is neither atomic across multiple owners nor atomic with the external action itself.Applications requiring either property need a transaction mechanism spanning the relevant boundary.
  • Engineering choices such as connection reuse, metadata placement, and artifact access can shift the measured coordination-cost crossover.

7 Conclusion

Stale-plan execution is a lineage failure in which current state coexists with an obsolete derivation. PlanFence records exact parents, validates declared dependencies, replans once, and fails closed, with cost advantages that depend on churn and dependency sparsity.

  • PlanFence records exact parents, validates declared dependencies, replans once, and fails closed.
  • Proactive synchronization has lower coordination stall at low update rates, while PlanFence avoids repeated coordination as churn grows.
  • Against batched all-key validation, PlanFence lowers measured stall and traffic when actions depend on a sparse subset of shared state.That advantage vanishes as the dependency set approaches the full keyspace.

A Implementation Details

The implementation uses replicated or centralized SQLite memory, authenticated TCP, immutable public records, and paired schedules so policy behavior can be compared under controlled conditions.

  • Five agent processes participate in the implementation and harness.
  • Replicated methods use one SQLite memory process per agent, while centralized lineage uses one shared SQLite memory process.
  • All communication uses authenticated TCP, and public records are immutable JSON objects stored in durable SQLite stores.
  • Paired policies receive the same initial records and schedules, with network impairments beginning only after setup.Trials terminating before any policy decision because of infrastructure failure are rerun.
  • Each public version stores its semantic key, immutable record ID, authoritative owner, monotone owner sequence, exact parent IDs, record type, content size, and public content or content address.

A.1 Metrics and statistical analysis

The evaluation combines controlled live workflows, replay, and statistical conventions to isolate memory-policy behavior while measuring safety, waiting time, and traffic under matched conditions.

  • Metrics and statistical analysis: Binary endpoints are reported as raw counts, with one-sided 95% exact-binomial upper bounds of 0.90% for 0/330, 9.5% for 0/30, and 0.023% for 0/13,200.
  • Metrics and statistical analysis: Cost comparisons pair identical schedules and use 2,000 bootstrap draws that resample the three workflow families as clusters.
  • Metrics and statistical analysis: A 10% reduction in median stall or traffic is treated as practically meaningful when safety does not weaken and availability falls by no more than five percentage points.
  • Validation procedure: The protected-action path validates dependencies, refreshes changed records, replans once with isolated history, and revalidates before propagating or blocking.
  • Exploratory live-workflow audit: In the exploratory audit, 15 cases issued an invalid action after the executor read the revised requirement because the generated plan remained tied to the initial requirement.
  • Matched controlled-live check: In the matched live study, owner-head freshness fails all 30 tasks, while centralized lineage and PlanFence complete 30/30 tasks without invalid actions and with one successful replan per task.The two safe methods unnecessarily repeat 4 and 10 valid auditor actions, respectively.

A.6 Evaluation coverage

The evaluation combines controlled live workflows with a matched keyspace study and a separate artifact control. Together, these tests cover lineage safety, coordination cost, and payload-path safety.

  • 13,200/13,200 actions complete with valid lineage in the matched keyspace study.The study supplies the scope-cost comparison.
  • 15,360/15,360 artifact-control actions complete with zero lineage violations.The control verifies payload-path safety rather than comparative stall.
  • The artifact control uses a different action path, so it supports payload-path safety but not comparative stall.

B Controlled-replay ablations

Controlled replay compares synchronization policies, exact-lineage validation, and learned policy selection across update rates, keyspaces, traces, and workload shifts. The results identify conditional cost boundaries while preserving deterministic lineage safety.

  • Synchronization cadence: Lower stall at low update rates favors proactive synchronization, while PLANFENCE avoids repeated update-path coordination as updates grow.
  • Independent AT&T trace phases: PLANFENCE has lower median stall and traffic in all six paired aggregates across independently replayed AT&T trace offsets.Both exact-lineage methods complete every action.
  • Dependency scope: At d = 1, PLANFENCE lowers stall and traffic; at d = 2, stall is a practical tie while traffic remains lower; at d = 8 = |X |, both endpoints are practical ties.
  • Learned policy selection: Selectors are trained from 1,332 controlled-replay examples with disjoint OOD blocks for trace, update-rate, keyspace, and compound shifts.Selectors receive pre-action workload dimensions and static trace calibration, not workflow outcomes or future trace events.
  • Learned policy selection: 95.0-96.7% safe near-optimal selection occurs for learned models on ID examples, compared with 89.4% for the transparent rule.Under shift, learned models fall to 84.4-94.2%, and none passes all four OOD blocks after the stated dominance criteria.

C Validation assumptions and component sensitivities

The ablations test the components required for safe and available execution: complete dependency contracts, full lineage traversal, replanning, and fail-closed validation. Omitting dependencies increases unsafe issuance, while fail-closed behavior blocks incomplete validation.

  • Lineage traversal: Full lineage traversal authorizes intact chains through depth eight, whereas direct-parent checking works only at depth one.
  • Replanning: 3,000 detected races become valid actions with replanning, while validation without replanning blocks all 3,000.
  • Dependency contracts: Unsafe issuance rises from 0% to 37.4% as the omission probability reaches 50%.The dependency-contract experiment independently omits three of four true dependencies.
  • Failure handling: Fail-closed validation blocks all four tested failure cases with no issued action, while fail-open validation issues an invalid action in all four.The cases include owner outage, missing lineage, malformed owner heads, and a second version change.
Loading 2609.03340v1…