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

arXiv: https://arxiv.org/abs/2608.10509 · HTML: https://mlsanity.com/paper/2608.10509/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use.
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 11 Aug 2026.

## Placed in

- LLM agents and tool use / [Agent threats, guardrails and governance](https://mlsanity.com/agents/agent-threats-guardrails-and-governance/)

## Builds on (most cited first, 16 of 16)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model Society](https://mlsanity.com/paper/2303.17760/) (2023)
- [MemGPT: Towards LLMs as Operating Systems](https://mlsanity.com/paper/2310.08560/) (2023)
- [A Survey on the Memory Mechanism of Large Language Model based Agents](https://mlsanity.com/paper/2404.13501/) (2024)
- [MemoRAG: Boosting Long Context Processing with Global Memory-Enhanced Retrieval Augmentation](https://mlsanity.com/paper/2409.05591/) (2024)
- [From Untrusted Input to Trusted Memory: A Systematic Study of Memory Poisoning Attacks in LLM Agents](https://mlsanity.com/paper/2606.04329/) (2026)
- [INMS: Memory Sharing for Large Language Model based Agents](https://mlsanity.com/paper/2404.09982/) (2024)
- [Hidden in Memory: Sleeper Memory Poisoning in LLM Agents](https://mlsanity.com/paper/2605.15338/) (2026)
- [MemLineage: Lineage-Guided Enforcement for LLM Agent Memory](https://mlsanity.com/paper/2605.14421/) (2026)
- [Governed Shared Memory for Multi-Agent LLM Systems](https://mlsanity.com/paper/2606.24535/) (2026)
- [Hijacking Agent Memory: Stealthy Trojan Attacks Through Conversational Interaction](https://mlsanity.com/paper/2605.29960/) (2026)

## Built on by (most cited first, 9 of 9)

- [Modality Disentangled Learning for Incomplete Multimodal Emotion Recognition: A Primitive Memory Distillation Perspective](https://mlsanity.com/paper/2608.30563/) (2026)
- [Explicit State Elicitation Is Not Enough: A Controlled Audit of Memory-Policy Classification](https://mlsanity.com/paper/2608.17247/) (2026)
- [Noise Floor Audit for Agent Benchmarks](https://mlsanity.com/paper/2608.22331/) (2026)
- [DIAG: Diagnostic Iterative Alignment and Generation for Data-Efficient Mathematical Preference Distillation](https://mlsanity.com/paper/2608.22806/) (2026)
- [Whose record is this? Diagnosing and authorizing record use in personalized multimodal models](https://mlsanity.com/paper/2609.04801/) (2026)
- [AkasicMEM: Governed Enterprise Memory for Agents](https://mlsanity.com/paper/2609.25563/) (2026)
- [Audience-Bound Persistent Memory: Authorization Across the Memory Lifecycle](https://mlsanity.com/paper/2609.36373/) (2026)
- [Copies or Sources? Measuring How LLM Aggregators Count Restated Evidence in Multi-Agent Systems](https://mlsanity.com/paper/2610.06192/) (2026)
- [The Right Memory in the Wrong Context: Verifying Retrieval Admissibility in Long-Term Agent Memory](https://mlsanity.com/paper/2610.07309/) (2026)

## Abstract (arXiv)

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 textscAllow 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.