Relevant Does Not Mean Authorized

An AI agent can retrieve the most relevant memory in its system and still have no right to use it.

MAP-Graph: Provenance-Aware Shared Memory for Multi-Agent Workflows tests an architecture that treats relevance, trust and permission as separate decisions. It carries restrictions through derived memories, filters permission-ineligible evidence before ranking, and checks the surviving evidence again when an agent proposes an action.

The paper was submitted to arXiv on August 11 at 05:31:18 UTC and appeared in the August 12 cs.AI batch. It is included through Keelbase Signal's August 13 catch-up review; the subject-batch appearance is the discovery route, not a new publication event.

A summary should not erase its source's restrictions

Shared memory turns previous observations, messages and tool outputs into reusable execution state. That reuse becomes dangerous when transformation changes the text but hides the conditions attached to its source. A summary may no longer look private, poisoned, untrusted or revoked even though it was derived from material carrying exactly those restrictions.

MAP-Graph records agents, sources, messages, memories, claims, tools and actions in a typed provenance graph. When a new memory is written from existing material, the implementation records its ancestry and carries forward the intersection of the referenced permission scopes.

At retrieval time, a binary permission check removes ineligible records before semantic ranking. The remaining candidates are scored by relevance and a multiplicative path-trust value derived from their recorded ancestry. That ordering matters: permission is not represented as a soft penalty that an extremely relevant result can overcome.

The most relevant evidence should never outrank a hard authorization boundary.

Source: MAP-Graph (opens in a new tab), submitted August 11, 2026.

Retrieval permission is not execution permission

Evidence that is acceptable for a low-risk answer may be insufficient for a consequential external action. MAP-Graph therefore makes a second decision after the proposed action is known.

The action-time gate rechecks supporting memories against their ancestry, current permission state and the risk assigned to the action. It can return Allow, Block, Reverify, Redact or AskUser. Affected descendants remain marked in the graph rather than being erased, preserving the lineage needed to explain why a record was constrained.

This extends the recent Keelbase Signal sequence. Authority Is a Chain of Evidence argued that authorization depends on preserved lineage. The Policy Check Needs a Receipt asked whether an enforcement step can prove that it ran. MAP-Graph adds another boundary: the evidence supporting an action must itself be admissible for the requesting agent and the action being attempted.

The architectural lesson is narrower than “use a graph.” Provenance becomes operational only when it changes what the system may retrieve, what it may use, and what requires re-verification before execution.

The benchmark shows why aggregate utility can mislead

The authors evaluate MAP-Graph on 2,700 synthetic tasks per method across corporate workflow, software engineering and research assistance. The tasks cover clean utility, poisoned propagation, private leakage, permission revocation, action-risk sensitivity and compression overhead.

MAP-Graph reports 94.96% task success, 72.70% exact decision accuracy and 90.22% clean success. In the paper's main table, it records no successful poisoned-memory attacks, private leaks, unauthorized reads or post-revocation allows under the benchmark's definitions.

The most revealing ablation removes the hard permission filter. Overall task success rises from 94.96% to 96.00% and exact accuracy rises from 72.70% to 78.63%, but every observed unauthorized read succeeds. A system optimized only for aggregate task performance could therefore look better while violating the access boundary it was supposed to enforce.

Removing the action-time gate produces the opposite warning. Clean success remains close to the full system, but task success falls to 69.44% and the reported poisoned-memory attack success rate rises to 34.89%. Retrieval controls alone do not govern what happens when evidence is converted into an action.

Controlled evidence is not deployment proof

The evaluation is deliberately synthetic. It supplies explicit ownership, visibility, trust, revocation and action-risk metadata; MAP-Graph does not infer a universal notion of truth or permission from open-ended language. No real external side effect is executed.

The main experiment uses Qwen2.5-7B-Instruct at temperature zero, fixed role order, one interaction round and one run per method. Its confidence intervals capture variation across semantic task families, not nondeterminism across repeated model runs. The three-backbone transfer study uses a stratified 540-task subset rather than the full benchmark.

Several comparison systems are benchmark adaptations, not faithful reimplementations. The benchmark also gives MAP-Graph the exact structured provenance and policy fields its mechanism is designed to use. Those choices make the experiment useful for isolating components, but they do not establish deployment-scale reliability, correct policy construction, complete lineage capture or safe behavior when metadata is missing or wrong.

The graph resets between tasks, so the experiment addresses within-task coordination rather than long-lived cross-session accumulation. It implements explicit revocation events but does not provide generic contradiction detection, temporal supersession or open-domain conflict resolution.

Govern the evidence before it becomes authority

The strongest conclusion is not that every agent memory needs MAP-Graph's exact schema or thresholds. It is that relevance, trust and authorization should not collapse into one retrieval score.

A governed system needs hard permission gates that similarity cannot override, inherited restrictions that survive transformation, action-specific evidence requirements, and an auditable explanation when a proposed action is blocked or sent for review. If any of those decisions depend on incomplete or incorrect metadata, the resulting control can still fail.

For governed autonomous systems, memory is not merely context. Once it supports a decision or tool call, it becomes part of the authority path—and should be controlled accordingly.

Sources and limitations

MAP-Graph is an author-reported preprint evaluated on a controlled synthetic benchmark. It does not establish production safety, correct policy semantics, complete mediation, reliable open-domain provenance capture or deployment-scale performance.

• MAP-Graph: Provenance-Aware Shared Memory for Multi-Agent Workflows (opens in a new tab)
• Supporting research considered in the catch-up review: Dependency-Guided Rollback Repair (opens in a new tab), REDAgentBench (opens in a new tab), Catastrophic Remembering (opens in a new tab), MEGA (opens in a new tab), and SkillZip (opens in a new tab)
• Genuine in-window market evidence reviewed but not promoted as a structured record: OpenAI — From assistance to execution (opens in a new tab)
• Same-day product announcements excluded under fail-closed timing because their primary pages expose no exact publication time: GitHub Agent Plugins 1.0 (opens in a new tab) and GitHub organization rule insights (opens in a new tab)