REVIEW 4 major objections 4 minor 40 references
MAP-Graph: Provenance-Aware Shared Memory for Multi-Agent Workflows
T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Provenance can act as an operational control signal for multi-agent shared memory, not just post-hoc audit metadata.
desk verdict MAP-Graph offers a genuinely useful integration of permission filtering, path trust, and action gating for agent shared memory, but the undisclosed oracle-label rule makes the headline numbers unverifiable as published. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is a typed execution-provenance graph, a heterogeneous directed graph whose nodes are agents, sources, memories, claims, and actions, and whose edges record derivation, summarization, read/write, verification, invalidation, and action use. The argument runs on the multiplicative path-trust identity $\rho(m,a)=\mathrm{clip}_{[0,1]}\big(S(m)\,I(m)\,F(m)\,P(m,a)\,V(m)\,A(m)\big)$, combining source trust, path integrity, transformation factor, permission validity, verification bonus, and writer reliability, with final rank $\mathrm{Score}(m,q,a)=s(m,q)\,\rho(m,a)$. This factorization does the load-bearing work: a binary permission filter removes candidates before ranking, while trust only scales surviving scores, so a highly similar record cannot outrank an access restriction; recursive traversal of the recorded ancestry makes multi-step restrictions visible; and a separate action-time gate, with risk-indexed thresholds, re-checks evidence once the proposed action is known. The graph is built only from observable execution traces and explicit metadata, not from private chain-of-thought.
What would settle it
Systematically vary the action-gate thresholds (0.30, 0.60, 0.85) and the path-trust penalties (0.25, 0.45, 0.15), or regenerate the oracle labels with an independently stated admissibility rule; if the 0% attack-success, leakage, and revocation rates do not survive, the operational-control claim is not robust.
Extended reading notes
Core claim
The paper's central claim is that provenance — the recorded lineage of which sources and derivations produced a memory — is sufficient to govern both retrieval and action-time admissibility, provided hard authorization is kept separate from graded trust. The proposed MAP-Graph builds a task-scoped typed execution graph with nodes for users, agents, tools, resources, messages, memories, claims, and actions, and edges for derivation, summarization, reading, writing, verification, invalidation, and action use. Retrieval first applies a binary permission check, then ranks only eligible memories by semantic similarity times a clipped multiplicative path trust that compounds penalties for untrusted, private, or revoked ancestry; an action-time re-evaluation blocks high-risk actions supported by affected memories while retaining their lineage for audit. In the evaluated synthetic setting, this reaches 94.96% task success and 72.70% exact decision accuracy with 0% observed unauthorized reads, attack success, leakage, and revocation violations across 2,700 tasks, and the exact-accuracy and access-enforcement advantages transfer across three language-model backbones. The authors frame these as single-run controlled results, not deployment-scale claims.
Load-bearing premise
The results stand on the assumption that the benchmark's synthetic task labels correctly define what should be allowed, together with hand-set trust and risk thresholds that the paper never varies.
Editorial extensions
If this is right
- Shared-memory systems can implement admissibility as a deterministic pipeline: permission filter, trust rerank, action gate, rather than relying on the model to infer restrictions from content.
- A single memory can be admissible for a low-risk answer yet inadmissible for a high-risk external action, because the decision is re-taken with action risk in view.
- Affected records need not be deleted: retaining them with their ancestry and marking them affected preserves audit evidence while blocking their use.
- Evaluation of governed memory should instrument the read boundary alongside aggregate utility, because utility can rise even as unauthorized reads occur.
- Exact decision quality and access enforcement can transfer across different generation backbones even when utility does not.
Reading between the lines
- Inference: If the hard/graded factorization generalizes, permission-tagged documents in ordinary retrieval pipelines could be filtered before ranking using the same pattern, with restrictions inherited through derivation steps rather than only through the memory layer's own writes.
- Inference: A testable extension is a sensitivity sweep of the hand-set constants; the claim that safety comes from provenance would be stronger if the 0% attack-success, leakage, and revocation rates survive modest changes to the listed thresholds and penalties.
- Inference: The paper's own residual safety errors concentrate in the action-risk group, which suggests that the next lever is better risk calibration rather than more provenance detail.
- Inference: The current design resets graph and vector state between tasks, so the results speak to within-task coordination; extending the same provenance machinery across sessions would require a policy for how permission scopes and trust levels compose across task boundaries.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents MAP-Graph, a provenance-aware shared-memory layer for multi-agent LLM workflows. MAP-Graph represents agents, sources, memories, claims, and actions in a typed execution graph; at retrieval it applies a hard permission filter, then reranks eligible memories by semantic similarity times a multiplicative path-trust score computed from recorded ancestry, and finally applies a risk-sensitive action-time gate that can return Allow, Block, Reverify, Redact, or AskUser. The evaluation is a controlled synthetic benchmark of 2,700 tasks across three domains, with seven baselines, six ablations, and a three-backbone transfer subset. The headline results are 94.96% task success, 72.70% exact decision accuracy, and 0% observed ASR, leakage, and revocation violations, with the caveat that these are single-run temperature-0 results. The paper argues that provenance can serve as an operational control signal rather than only post-hoc audit metadata.
Significance. If the results hold, the paper makes a useful contribution: it cleanly separates hard authorization from graded trust, introduces an action-indexed gate that addresses a real limitation of retrieval-only policies, and its access-boundary metrics (UAcc, leakage, revocation) are more informative than utility-only evaluation. The appendix documentation is unusually detailed for the architecture and operation semantics, and the ablations (especially the no-permission-filter variant, where utility rises while unauthorized access jumps to 100%) give concrete evidence that aggregate utility can mask access-control failures. The main empirical claim, however, is only as strong as the undisclosed oracle-labeling rule and the unexamined hand-set constants; as published, the central evaluation is not fully verifiable.
major comments (4)
- [Section 4.1 and Appendix C] The oracle label-generation rule is not documented. The benchmark is described as having 960 Allow, 1,140 Block, 210 Reverify, and 390 Redact labels, and the sanitizer removes the 'oracle decision, evaluator rationale, experiment and family identifiers, variant metadata, the top-level evaluator canary annotation, and every should_be_used annotation' before agents run, but Appendix C never states the rule that produced these labels from the task fields. Since Acc, TSR, Unsafe, ASR, Leakage, and Revocation are all computed relative to these labels, the readers cannot determine whether the labels encode an independent admissibility criterion or are generated by a rule that consumes the same visibility, ownership, trust, risk, and revocation fields that MAP-Graph's deterministic rules consume. Please state the exact label-generation rule, or better, release the generator code and data, and confirm that the rule was not derived from MAP-Graph's own scoring or thresholds.
- [Section 3.4 and Appendix A.1] The hand-set constants and thresholds are load-bearing but receive no sensitivity analysis. The gate thresholds (0.30 for answers, 0.60 for low/medium risk, 0.85 for high risk), the path-integrity penalties (0.25, 0.45, 0.15), transformation losses, verification bonus, and default source trust and writer reliability (0.80, 0.95) enter directly into the multiplicative trust score and the gate decisions. The headline 0% ASR, leakage, and revocation, and even the 94.96% TSR, are single-point estimates evaluated at one manually chosen parameter vector. Please report a sensitivity sweep over these parameters (at least the gate thresholds and the main integrity penalties) to show that the safety and utility conclusions are not knife-edge artifacts of the chosen values.
- [Section 4.3 and Appendix E] The empirical claims rest on a single temperature-0 run, and the reported confidence intervals are cluster-bootstrap intervals over semantic families within that fixed run, not over inference nondeterminism. The paper acknowledges this, but the central claim that provenance 'can be an operational control signal' is supported by point estimates from a single seed and a single run of each method. Since remote API calls at temperature 0 can still exhibit sampling nondeterminism and token-cap truncations (3.89–9.08% of calls reach the cap), please provide at least a small number of repeated runs (or multiple seeds) for the main comparison and the key ablations, and report the resulting variance in the safety metrics, especially the 0% rates.
- [Section 3.3] The write-time scope-intersection rule is stated as the mechanism that 'carries access restrictions into newly derived records,' but its correctness is not analyzed or tested in the scenarios where a derived memory references multiple sources with different ownership scopes, or where a source is revoked after a multi-step derivation chain. The current benchmark has one scenario class per group and a structured set of fields, so it may not exercise conflicting-scope cases or delayed revocation through deep ancestry. Please either provide a formal argument for the intersection rule with respect to the CanRead check, or add targeted tests that vary the number and conflict of referenced scopes and the depth of the derivation chain.
minor comments (4)
- [Appendix C.1] The statement 'if the final structured action cannot be parsed, the harness recovers the public action type and risk from the task schema and uses the retrieved records as support' should specify how often this fallback occurred and whether it was applied uniformly across baseline methods, since it affects the comparability of the gate inputs.
- [Section 4.5 / Table 3] The backbone transfer section says MAP-Graph 'leads TSR on Qwen and Llama' but on GLM it trails B6 by 2.59 points; the accompanying text currently mentions this as a utility–safety trade-off, but a clearer statement of whether this difference is within the bootstrap interval of the subset would help the reader interpret the transfer claim.
- [Appendix F.6] The error analysis reports 601 safe-but-non-exact interventions and 95 unnecessary interventions on allow cases; it would be helpful to add a short breakdown of how the 95 cases are distributed across the six experiment groups, since 'unnecessary intervention' on clean allow tasks is a different failure mode from a non-exact block in a poisoned task.
- [References] Several references have inconsistent formatting, including 'Ligh- tRAG' split across a line break and missing venue/pages details for some arXiv-only entries; please normalize the bibliography to the journal's style.
Circularity Check
No demonstrated circularity: MAP-Graph's decisions are deterministic rules over retained metadata, the oracle labels are sanitized out of the runtime inputs, and the paper's central comparison rests on ablations and a flat-metadata control rather than on a self-citation or a fitted prediction.
full rationale
No circular step can be exhibited from the paper's own equations or citations. The decision pipeline is stated as a deterministic policy over recorded provenance and explicit metadata (Sections 3.3-3.4, Eq. 4), and the oracle labels are removed before execution: 'The runtime sanitizer removes the oracle decision, evaluator rationale, experiment and family identifiers, variant metadata, the top-level evaluator canary annotation, and every should_be_used annotation before either the agents or memory backend receive a task.' Thus exact accuracy is not computed from the labels at inference time. The path-trust factors and gate thresholds are hand-set constants, not fitted to the benchmark, and the paper discloses them fully (Appendix A.1, Section 4.3). The ablations and the B6 flat-metadata control give the central claim independent content: removing the gate or permission filter sharply changes the measured failure modes, which is evidence that the components, rather than the oracle labels alone, drive the result. The most serious interpretability gap is that Appendix C never states the rule that generated the 2,700 oracle labels; if that rule were the same deterministic policy over the same risk, visibility, ownership, and trust fields, then exact accuracy would partly be a closed-loop check. However, the paper does not provide enough detail to exhibit that equivalence, and no equation or citation defines the oracle labels in terms of MAP-Graph's outputs or vice versa. Under the hard rule requiring a quoted reduction, this is a verification limitation, not established circularity. Self-citations (e.g., MIRIX in related work) are background references and are not load-bearing for the main derivation. Therefore the score is 0.
Assumptions & free parameters
free parameters (8)
- theta_answer =
0.30
- theta_low_medium =
0.60
- theta_high =
0.85
- default_source_trust =
0.80
- path_integrity_penalties =
0.25, 0.45, 0.15
- transformation_loss_rates =
0.08, 0.10, 0.03, cap 0.65
- verification_bonus =
1.20 cap, +0.05 per high-trust ancestor
- default_writer_reliability =
0.95
assumptions (4)
- domain assumption Observed workflow events and task metadata are sufficient to reconstruct the true derivation ancestry of every memory.
- domain assumption The structured oracle labels in the synthetic benchmark are correct ground truth for admissibility decisions.
- ad hoc to paper Hand-set constants and thresholds generalize across domains, scenarios, and backbones without retuning.
- ad hoc to paper Write-time scope intersection correctly captures all inherited access restrictions.
Cite this review
Pith. "Pith review of MAP-Graph: Provenance-Aware Shared Memory for Multi-Agent Workflows." pith.science (2026). https://pith.science/paper/ETK5S5KL
@misc{pith2026260810509,
author = {Pith},
title = {Pith review of: MAP-Graph: Provenance-Aware Shared Memory for Multi-Agent Workflows},
year = {2026},
howpublished = {\url{https://pith.science/paper/ETK5S5KL}},
note = {Machine review of arXiv:2608.10509}
}
read the original 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.
Figures
Reference graph
Works this paper leans on
-
[1]
Retrieval-Augmented Generation for Knowledge-Intensive
Lewis, Patrick and Perez, Ethan and Piktus, Aleksandra and Petroni, Fabio and Karpukhin, Vladimir and Goyal, Naman and K. Retrieval-Augmented Generation for Knowledge-Intensive. Advances in Neural Information Processing Systems , volume =. 2020 , url =
2020
-
[2]
2020 , url =
Guu, Kelvin and Lee, Kenton and Tung, Zora and Pasupat, Panupong and Chang, Ming-Wei , booktitle =. 2020 , url =
2020
-
[3]
Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing , pages =
Dense Passage Retrieval for Open-Domain Question Answering , author =. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing , pages =. 2020 , address =. doi:10.18653/v1/2020.emnlp-main.550 , url =
-
[4]
Transactions of the Association for Computational Linguistics , volume =
Lost in the Middle: How Language Models Use Long Contexts , author =. Transactions of the Association for Computational Linguistics , volume =. 2024 , doi =
2024
-
[5]
Edge, Darren and Trinh, Ha and Cheng, Newman and Bradley, Joshua and Chao, Alex and Mody, Apurva and Truitt, Steven and Metropolitansky, Dasha and Ness, Robert Osazuwa and Larson, Jonathan , journal =. From Local to Global: A Graph. 2024 , url =
work page 2024
-
[6]
Findings of the Association for Computational Linguistics: EMNLP 2025 , pages =
Guo, Zirui and Xia, Lianghao and Yu, Yanhua and Ao, Tu and Huang, Chao , editor =. Findings of the Association for Computational Linguistics: EMNLP 2025 , pages =. 2025 , month = nov, address =. doi:10.18653/v1/2025.findings-emnlp.568 , url =
-
[7]
Advances in Neural Information Processing Systems , volume =
Guti. Advances in Neural Information Processing Systems , volume =. 2024 , url =
work page 2024
-
[8]
Qian, Hongjin and Liu, Zheng and Zhang, Peitian and Mao, Kelong and Lian, Defu and Dou, Zhicheng and Huang, Tiejun , booktitle =. 2025 , address =. doi:10.1145/3696410.3714805 , url =
arXiv 2025
Show all 40 references
-
[9]
2023 , url =
Yao, Shunyu and Zhao, Jeffrey and Yu, Dian and Du, Nan and Shafran, Izhak and Narasimhan, Karthik and Cao, Yuan , booktitle =. 2023 , url =
2023
-
[10]
Advances in Neural Information Processing Systems , volume =
Reflexion: Language Agents with Verbal Reinforcement Learning , author =. Advances in Neural Information Processing Systems , volume =. 2023 , url =
2023
-
[11]
Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology , series =
Generative Agents: Interactive Simulacra of Human Behavior , author =. Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology , series =. 2023 , pages =. doi:10.1145/3586183.3606763 , url =
2023
-
[12]
2023 , url =
Li, Guohao and Hammoud, Hasan Abed Al Kader and Itani, Hani and Khizbullin, Dmitrii and Ghanem, Bernard , booktitle =. 2023 , url =
2023
-
[13]
and Burger, Doug and Wang, Chi , booktitle =
Wu, Qingyun and Bansal, Gagan and Zhang, Jieyu and Wu, Yiran and Li, Beibin and Zhu, Erkang and Jiang, Li and Zhang, Xiaoyun and Zhang, Shaokun and Liu, Jiale and Awadallah, Ahmed Hassan and White, Ryen W. and Burger, Doug and Wang, Chi , booktitle =. 2024 , url =
2024
-
[14]
International Conference on Learning Representations , year =
Hong, Sirui and Zhuge, Mingchen and Chen, Jiaqi and Zheng, Xiawu and Cheng, Yuheng and Zhang, Ceyao and Wang, Jinlin and Wang, Zili and Yau, Steven Ka Shing and Lin, Zijuan and Zhou, Liyang and Ran, Chenyu and Xiao, Lingfeng and Wu, Chenglin and Schmidhuber, J. International C...
-
[15]
arXiv preprint arXiv:2305.16291 , year =
Voyager: An Open-Ended Embodied Agent with Large Language Models , author =. arXiv preprint arXiv:2305.16291 , year =
-
[16]
and Stoica, Ion and Gonzalez, Joseph E
Packer, Charles and Wooders, Sarah and Lin, Kevin and Fang, Vivian and Patil, Shishir G. and Stoica, Ion and Gonzalez, Joseph E. , journal =. 2023 , url =
2023
-
[17]
2024 , doi =
Zhong, Wanjun and Guo, Lianghong and Gao, Qiqi and Ye, He and Wang, Yanlin , booktitle =. 2024 , doi =
2024
-
[18]
Advances in Neural Information Processing Systems , volume =
Augmenting Language Models with Long-Term Memory , author =. Advances in Neural Information Processing Systems , volume =. 2023 , url =
2023
-
[19]
ACM Transactions on Information Systems , volume =
A Survey on the Memory Mechanism of Large Language Model-based Agents , author =. ACM Transactions on Information Systems , volume =. 2025 , doi =
2025
-
[20]
2024 , url =
Gao, Hang and Zhang, Yongfeng , journal =. 2024 , url =
2024
-
[21]
Collaborative Memory: Multi-User Memory Sharing in
Rezazadeh, Alireza and Li, Zichao and Lou, Ange and Zhao, Yuying and Wei, Wei and Bao, Yujia , journal =. Collaborative Memory: Multi-User Memory Sharing in. 2025 , url =
2025
-
[22]
2025 , url =
Zhang, Guibin and Fu, Muxin and Wan, Guancheng and Yu, Miao and Wang, Kun and Yan, Shuicheng , journal =. 2025 , url =
2025
-
[23]
2025 , url =
Wang, Yu and Chen, Xi , journal =. 2025 , url =
2025
-
[24]
Scaling Teams or Scaling Time? Memory Enabled Lifelong Learning in
Wu, Shanglin and Luo, Yuyang and Liang, Yueqing and Shi, Kaiwen and Ye, Yanfang and Payani, Ali and Shu, Kai , journal =. Scaling Teams or Scaling Time? Memory Enabled Lifelong Learning in. 2026 , url =
2026
-
[25]
Governed Shared Memory for Multi-Agent
Margalit, Yanki and Cohen-Inger, Nurit and Avram, Erni and Taig, Ran and Margalit, Oded , journal =. Governed Shared Memory for Multi-Agent. 2026 , url =
2026
- [26]
-
[27]
2013 , url =
Moreau, Luc and Missier, Paolo , institution =. 2013 , url =
2013
-
[28]
Missier, Paolo and Belhajjame, Khalid and Cheney, James , booktitle =. The. 2013 , doi =
2013
-
[29]
2024 , url =
Dong, Liming and Lu, Qinghua and Zhu, Liming , journal =. 2024 , url =
2024
-
[30]
2026 , url =
AlSayyad, Adam and Huang, Kelvin Yuxiang and Pal, Richik , journal =. 2026 , url =
2026
-
[31]
From Agent Traces to Trust: A Survey of Evidence Tracing and Execution Provenance in
Wang, Yiqi and Zhang, Jiaqi and Cai, Taotao and Liu, Zirui and Sun, Qingqiang and Sun, Zequn and Wu, Zhangkai and Dong, Manqing and Zheng, Mingkai and Yin, Xuefei and Zhu, Yanming , journal =. From Agent Traces to Trust: A Survey of Evidence Tracing and Execution Provenance in...
2026
-
[32]
Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing , pages =
Enabling Large Language Models to Generate Text with Citations , author =. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing , pages =. 2023 , address =. doi:10.18653/v1/2023.emnlp-main.398 , url =
2023 doi
-
[33]
2023 , address =
Min, Sewon and Krishna, Kalpesh and Lyu, Xinxi and Lewis, Mike and Yih, Wen-tau and Koh, Pang Wei and Iyyer, Mohit and Zettlemoyer, Luke and Hajishirzi, Hannaneh , booktitle =. 2023 , address =. doi:10.18653/v1/2023.emnlp-main.741 , url =
2023 doi
-
[34]
Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pages =
Niu, Cheng and Wu, Yuanhao and Zhu, Juno and Xu, Siliang and Shum, KaShun and Zhong, Randy and Song, Juntong and Zhang, Tong , editor =. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pages =. 2024 , month = au...
2024 doi
-
[35]
arXiv preprint arXiv:2502.06872 , year =
Towards Trustworthy Retrieval Augmented Generation for Large Language Models: A Survey , author =. arXiv preprint arXiv:2502.06872 , year =
-
[36]
2026 , url =
Chao, Hanxiang and Bai, Yihan and Sheng, Rui and Li, Tianle and Sun, Yushi , journal =. 2026 , url =
2026
-
[37]
From Untrusted Input to Trusted Memory: A Systematic Study of Memory Poisoning Attacks in
Dash, Pritam and Ge, Tongyu and Jain, Aditi and Shah, Tanmay and Shang, Zhiwei , journal =. From Untrusted Input to Trusted Memory: A Systematic Study of Memory Poisoning Attacks in. 2026 , url =
2026
-
[38]
Hidden in Memory: Sleeper Memory Poisoning in
Pulipaka, Sidharth and Hlebik, Stanislau and Raghav, Leonidas and Abdelnabi, Sahar and Raina, Vyas and Sheth, Ivaxi and Fritz, Mario , journal =. Hidden in Memory: Sleeper Memory Poisoning in. 2026 , url =
2026
-
[39]
2026 , url =
Zhang, Xuanye and Zheng, Yongsen and Xu, Zhuqin and Zhou, Kaiyu and Shen, Bowen and Ou, Haoran and Zhang, Tianwei and Lam, Kwok-Yan , journal =. 2026 , url =
2026
-
[40]
arXiv preprint arXiv:2605.29960 , year =
Hijacking Agent Memory: Stealthy Trojan Attacks Through Conversational Interaction , author =. arXiv preprint arXiv:2605.29960 , year =
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.