MAP-Graph: Provenance-Aware Shared Memory for Multi-Agent Workflows

• URL: http://arxiv.org/abs/2608.10509v1
• Date: Tue, 11 Aug 2026 05:31:18 GMT
• Title: MAP-Graph: Provenance-Aware Shared Memory for Multi-Agent Workflows
• Abstract summary: We introduce MAP-Graph, a provenance-aware memory layer that represents agents, sources, memories, claims, and actions in a typed execution graph.<n>It traces ancestry, excludes permission-ineligible records, reranks eligible memories by semantic similarity and multiplicative path trust, and applies a risk-sensitive gate before action execution while retaining affected lineage for audit.
• Score: 21.565934900490166
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shared memory helps language-model agents reuse information across long workflows, yet relevant evidence may not be admissible for a particular agent or action. Because restrictions propagate through derivations, summaries can conceal private, poisoned, untrusted, or revoked sources, enabling unauthorized reads or unsafe actions. Existing approaches provide semantic retrieval, scoped access, or lineage tracking, but do not clearly separate hard authorization from graded trust or adapt evidence requirements to action risk. We introduce MAP-Graph, a provenance-aware memory layer that represents agents, sources, memories, claims, and actions in a typed execution graph. It traces ancestry, excludes permission-ineligible records, reranks eligible memories by semantic similarity and multiplicative path trust, and applies a risk-sensitive gate before action execution while retaining affected lineage for audit. On a controlled benchmark of 2,700 synthetic tasks per method across three domains, MAP-Graph achieves 94.96\% overall task success, 72.70\% exact decision accuracy, and 90.22\% in the clean setting, where success requires a correct \textsc{Allow} rather than a safe intervention. Ablations isolate the roles of permission filtering, path trust, and action gating, while transfer tests with two additional backbones preserve the exact-decision and access-control advantages. These results support provenance as an operational control signal, rather than only post-hoc audit metadata, within the evaluated setting.

Related papers

• ROPE: Routed Origin Policy Enforcement against Indirect Prompt Injection [61.4148196085256]
  We present ROPE (Routed Origin Policy Enforcement), which is anchored in a structural notion of trust.<n>Our approach admits two provable guarantees: 1) at every step of a trajectory, no value whose only origin is attacker-writable content reaches an origin-guarded parameter, and 2) no rewording of an injection changes an admission decision.
  arXiv  Detail & Related papers  (2026-08-27T01:22:14Z)
• Agent Security Needs Redefinition through a Holistic Framework [46.88917910966891]
  Defenses ask whether an instruction looks malicious. Benchmarks ask whether an agent performs a harmful sounding action.<n>We operationalize contextual security through four properties that must hold jointly and be evaluated continuously across the agent's trajectory.
  arXiv  Detail & Related papers  (2026-07-24T06:43:09Z)
• DRNOISE: Benchmarking Deep Research Agents in Misleading Evidence Environments [51.049999642138]
  We introduce DRNOISE, a 100-task benchmark for answer recovery under misleading evidence.<n>Each task has a unique gold answer supported by two corroborating indirect record chains; the paired noisy condition adds one plausible document that states a conflicting answer directly.<n>Across agents with strong clean-task performance, this single intervention causes 66-88 percentage-point accuracy drops.
  arXiv  Detail & Related papers  (2026-07-19T15:20:40Z)
• Fantastic Adaptive Taxonomies and How to Use Them [100.20614173157708]
  AdaMAST converts execution traces into a compact, evidence-grounded failure taxonomy.<n>No code is hand-authored, no trace human-annotated.<n>In agent-system search, taxonomy-coded diagnoses of failed candidates outperform free-form.
  arXiv  Detail & Related papers  (2026-07-17T17:41:16Z)
• RedAct: Redacting Agent Capability Traces for Procedural Skill Protection [6.305785618804429]
  Execution traces contain rich procedural detail, including tool invocations, intermediate decisions, and error-recovery logic.<n>This detail can expose private procedural skills, allowing downstream methods to recover key formulas, thresholds, and strategies without access to model weights or skill files.<n>We introduce RedAct, a protected trace release framework that localizes protected key information, rewrites traces while preserving verifier-critical evidence, and embeds behavioral watermarks for downstream provenance analysis.
  arXiv  Detail & Related papers  (2026-06-09T12:57:50Z)
• Aligning Provenance with Authorization: A Dual-Graph Defense for LLM Agents [11.867868278947524]
  LLM-based agents are increasingly deployed in high-stakes scenarios such as email management, financial transactions, and code execution.<n>We propose AuthGraph, a dual-graph alignment defense framework that constructs two complementary graphs.<n>On AgentDojo, AuthGraph reduces the attack success rate from 40% to 1% while maintaining 76% task completion rate on GPT-4o; on AgentDyn, it reduces the attack success rate from 39% to 2% while preserving 51% utility.
  arXiv  Detail & Related papers  (2026-05-26T03:20:23Z)
• Verify-Gated Completion as Admission Control in a Governed Multi-Agent Runtime: A Bounded Architecture Case Study [0.6875312133832079]
  We study verify-gated completion as an admission-control pattern for governed multi-agent runtimes.<n>We show that under observed conditions, a read-only verify gate plus packetized admission records made completion decisions inspectable and fail-closed.
  arXiv  Detail & Related papers  (2026-05-18T07:52:13Z)
• AgentSys: Secure and Dynamic LLM Agents Through Explicit Hierarchical Memory Management [47.49917373646469]
  Existing defenses treat bloated memory as given and focus on remaining resilient.<n>We present AgentSys, a framework that defends against indirect prompt injection through explicit memory management.
  arXiv  Detail & Related papers  (2026-02-07T06:28:51Z)
• DoVer: Intervention-Driven Auto Debugging for LLM Multi-Agent Systems [48.971606069204825]
  DoVer is an intervention-driven debug framework for large language model (LLM)-based multi-agent systems.<n>It augments hypothesis generation with active verification through targeted interventions.<n>DoVer flips 18-28% of failed trials into successes, achieves up to 16% milestone progress, and validates or refutes 30-60% of failure hypotheses.
  arXiv  Detail & Related papers  (2025-12-07T09:23:48Z)
• Towards Copyright Protection for Knowledge Bases of Retrieval-augmented Language Models via Reasoning [58.57194301645823]
  Large language models (LLMs) are increasingly integrated into real-world personalized applications.<n>The valuable and often proprietary nature of the knowledge bases used in RAG introduces the risk of unauthorized usage by adversaries.<n>Existing methods that can be generalized as watermarking techniques to protect these knowledge bases typically involve poisoning or backdoor attacks.<n>We propose name for harmless' copyright protection of knowledge bases.
  arXiv  Detail & Related papers  (2025-02-10T09:15:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.