CoChat
Sign Up
PreprintCited by 1Access Control and TrustSecurity and Verification in ComputingPrivacy-Preserving Technologies in Data

Selection Integrity for LLM Graph Memory: An Accumulability Criterion for Information-Flow-Blind Retrieval

Open access
Fei, Zeming, Fei, Hongming, Wang, Xiaoyang, yang, Yang, Gope, Prosanta, Sikdar, Biplab, Zhang, Ying·2026·arXiv
DOI 10.48550/arxiv.2606.12290arXiv 2606.12290
Open this paper in CoChat — free accountOpen PDF

Abstract

Agent memory is moving to graphs, and the provenance defenses now being built for it all check one thing: the provenance of the records an agent retrieves. We show that this entire class of defense is blind by construction. A long-term graph memory runs a global selection step over writable graph structure, so structure that an untrusted principal writes changes \emph{which} authenticated facts are selected while the cited evidence stays fully authenticated; faithful information-flow control (IFC), checking the provenance of what the reader uses (all of it authenticated), makes the byte-identical decision to no defense at all, across document-QA substrates and real multi-session agent memory. In the most consequential instance, a no-source structural write silently misdirects $28$ irreversible ledger transfers over $499$ live actions: faithful IFC permits every one, and \authselect\ prevents every one. We then characterize exactly which memories are exposed: a selector admits the channel when its structural term can reallocate an $Ω(1)$ share of top-$k$ membership past a selected fact's margin. Personalized PageRank can, since a sourceless write reroutes conserved random-walk mass; a content-fixed reranker cannot, and Graphiti's node-distance, which leans on structure \emph{more} than PageRank does, stays immune. Reallocatability, not reliance, is the predictor. We prove the immune case in general and the open case under a chokepoint condition we verify. Closing the channel forces any provenance defense to recompute selection on the authenticated subgraph, which is what \authselect\ does, at zero over-block and $2$--$3\%$ latency.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2606.12290

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 49

  1. S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao, "ReAct: Synergizing reasoning and acting in language models," in International Conference on Learning Representations (ICLR), 2023.
  2. T. Schick, J. Dwivedi-Yu, R. Dessì, R. Raileanu, M. Lomeli, E. Ham- bro, L. Zettlemoyer, N. Cancedda, and T. Scialom, "Toolformer: Language models can teach themselves to use tools," in Advances in Neural Information Processing Systems (NeurIPS), 2023.
  3. N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao, "Reflexion: Language agents with verbal reinforcement learning," in Advances in Neural Information Processing Systems (NeurIPS), 2023.
  4. J. S. Park, J. C. O'Brien, C. J. Cai, M. R. Morris, P. Liang, and M. S. Bernstein, "Generative agents: Interactive simulacra of human behav- ior," in ACM Symposium on User Interface Software and Technology (UIST), 2023.
  5. Q. Wei, T. Yang, Y. Wang, X. Li, L. Li, Z. Yin, Y. Zhan, T. Holz, Z. Lin, and X. Wang, "A-MemGuard: A proactive defense framework for LLM-based agent memory," 2025, arXiv:2510.02373. [Online]. Available: https://arxiv.org/abs/2510.02373 · arXiv
  6. V. P. Bhardwaj, "SuperLocalMemory: Privacy-preserving multi- agent memory with Bayesian trust defense against memory poisoning," 2026, arXiv:2603.02240. [Online]. Available: https: //arxiv.org/abs/2603.02240 · arXiv
  7. Z. Lin, C. Li, and K. Chen, "A survey on the security of long-term memory in LLM agents: Toward mnemonic sovereignty," 2026, arXiv:2604.16548. [Online]. Available: https://arxiv.org/abs/ 2604.16548 · arXiv
  8. B. J. Gutiérrez, Y. Shu, Y. Gu, M. Yasunaga, and Y. Su, "HippoRAG: Neurobiologically inspired long-term memory for large language models," in Advances in Neural Information Processing Systems, 2024, arXiv:2405.14831. [Online]. Available: https://arxiv.org/abs/2405.14831 · arXiv
  9. B. J. Gutiérrez, Y. Shu, W. Qi, S. Zhou, and Y. Su, "From RAG to memory: Non-parametric continual learning for large language models," in International Conference on Machine Learning, 2025, arXiv:2502.14802. [Online]. Available: https://arxiv.org/abs/2502. 14802 · arXiv
  10. P. Rasmussen, P. Paliychuk, T. Beauvais, J. Ryan, and D. Chalef, "Zep: A temporal knowledge graph architecture for agent memory," 2025, arXiv:2501.13956. [Online]. Available: https://arxiv.org/abs/ 2501.13956 · arXiv
  11. G. Angeli, M. J. J. Premkumar, and C. D. Manning, "Leveraging linguistic structure for open domain information extraction," in An- nual Meeting of the Association for Computational Linguistics (ACL), 2015, pp. 344-354.
  12. G. Jeh and J. Widom, "Scaling personalized web search," in Interna- tional Conference on World Wide Web (WWW), 2003.
  13. H. Tong, C. Faloutsos, and J.-Y. Pan, "Fast random walk with restart and its applications," in IEEE International Conference on Data Mining (ICDM), 2006, pp. 613-622.
  14. V. Traag, L. Waltman, and N. J. van Eck, "From Louvain to Leiden: Guaranteeing well-connected communities," Scientific Reports, vol. 9, no. 1, p. 5233, 2019, arXiv:1810.08473. [Online]. Available: https://arxiv.org/abs/1810.08473 · arXiv
  15. K. Greshake, S. Abdelnabi, S. Mishra, C. Endres, T. Holz, and M. Fritz, "Not what you've signed up for: Compromising real-world LLM-integrated applications with indirect prompt injection," in ACM Workshop on Artificial Intelligence and Security (AISec), 2023, arXiv:2302.12173. [Online]. Available: https://arxiv.org/abs/ 2302.12173 · arXiv
  16. W. Zou, R. Geng, B. Wang, and J. Jia, "PoisonedRAG: Knowledge corruption attacks to retrieval-augmented generation of large language models," in USENIX Security Symposium, 2025, arXiv:2402.07867. [Online]. Available: https://arxiv.org/abs/2402.07867 · arXiv
  17. Z. Zhong, Z. Huang, A. Wettig, and D. Chen, "Poisoning retrieval corpora by injecting adversarial passages," in Conference on Empirical Methods in Natural Language Processing, 2023, arXiv:2310.19156. [Online]. Available: https://arxiv.org/abs/2310. 19156 · arXiv
  18. Z. Chen, Z. Xiang, C. Xiao, D. Song, and B. Li, "AgentPoison: Red-teaming LLM agents via poisoning memory or knowledge bases," in Advances in Neural Information Processing Systems, 2024, arXiv:2407.12784. [Online]. Available: https://arxiv.org/abs/ 2407.12784 · arXiv
  19. J. Liang, Y. Wang, C. Li, R. Zhu, T. Jiang, N. Gong, and T. Wang, "GraphRAG under fire," in IEEE Symposium on Security and Privacy, 2026, arXiv:2501.14050. [Online]. Available: https://arxiv.org/abs/2501.14050 · arXiv
  20. J. Wen, T. Chen, Z. Zheng, and C. Huang, "A few words can distort graphs: Knowledge poisoning attacks on graph-based retrieval-augmented generation of large language models," 2025, arXiv:2508.04276. [Online]. Available: https://arxiv.org/abs/2508. 04276 · arXiv
  21. B. Kereopa-Yorke, G. Diaz, H. Wright, R. Johnston, R. F. Del Rosario, and T. Lynar, "Oracle poisoning: Corrupting knowledge graphs to weaponise AI agent reasoning," 2026, arXiv:2605.09822. [Online]. Available: https://arxiv.org/abs/2605.09822 · arXiv
  22. R. Andersen, F. Chung, and K. Lang, "Local graph partitioning using PageRank vectors," in IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 475-486.
  23. G. Izacard, M. Caron, L. Hosseini, S. Riedel, P. Bojanowski, A. Joulin, and E. Grave, "Unsupervised dense information retrieval with contrastive learning," 2022, arXiv:2112.09118. [Online]. Available: https://arxiv.org/abs/2112.09118 · arXiv
  24. P. He, X. Liu, J. Gao, and W. Chen, "DeBERTa: Decoding-enhanced BERT with disentangled attention," in International Conference on Learning Representations, 2021, arXiv:2006.03654. [Online]. Available: https://arxiv.org/abs/2006.03654 · arXiv
  25. A. Maharana, D.-H. Lee, S. Tulyakov, M. Bansal, F. Barbieri, and Y. Fang, "Evaluating very long-term conversational memory of LLM agents," in Annual Meeting of the Association for Computational Linguistics, 2024, arXiv:2402.17753. [Online]. Available: https: //arxiv.org/abs/2402.17753 · arXiv
  26. Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. W. Cohen, R. Salakhutdinov, and C. D. Manning, "HotpotQA: A dataset for diverse, explainable multi-hop question answering," in Conference on Empirical Methods in Natural Language Processing, 2018, arXiv:1809.09600. [Online]. Available: https://arxiv.org/abs/1809.09600 · arXiv
  27. H. Trivedi, N. Balasubramanian, T. Khot, and A. Sabharwal, "MuSiQue: Multihop questions via single-hop question composition," Transactions of the Association for Computational Linguistics, vol. 10, 2022. [Online]. Available: https://doi.org/10.1162/tacl_a_ 00475 · DOI · Paper page
  28. X. Ho, A.-K. Duong Nguyen, S. Sugawara, and A. Aizawa, "Constructing a multi-hop QA dataset for comprehensive evaluation of reasoning steps," in International Conference on Computational Linguistics, 2020, arXiv:2011.01060. [Online]. Available: https: //arxiv.org/abs/2011.01060 · arXiv
  29. F. Perez and I. Ribeiro, "Ignore previous prompt: Attack techniques for language models," 2022, arXiv:2211.09527. [Online]. Available: https://arxiv.org/abs/2211.09527 · arXiv
  30. Y. Liu, Y. Jia, R. Geng, J. Jia, and N. Z. Gong, "Formalizing and benchmarking prompt injection attacks and defenses," in USENIX Security Symposium, 2024.
  31. Q. Zhan, Z. Liang, Z. Ying, and D. Kang, "InjecAgent: Benchmarking indirect prompt injections in tool-integrated large language model agents," in Findings of the Association for Computational Linguistics (ACL), 2024, pp. 10 471-10 506.
  32. E. Debenedetti, J. Zhang, M. Balunović, L. Beurer-Kellner, M. Fis- cher, and F. Tramèr, "AgentDojo: A dynamic environment to evaluate attacks and defenses for LLM agents," in Advances in Neural Infor- mation Processing Systems (Datasets and Benchmarks Track), 2024, arXiv:2406.13352. · arXiv
  33. E. Wallace, K. Xiao, R. Leike, L. Weng, J. Heidecke, and A. Beutel, "The instruction hierarchy: Training LLMs to prioritize privileged instructions," 2024, arXiv:2404.13208. [Online]. Available: https://arxiv.org/abs/2404.13208 · arXiv
  34. D. Zügner, A. Akbarnejad, and S. Günnemann, "Adversarial attacks on neural networks for graph data," in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2018, pp. 2847-2856.
  35. D. Zügner and S. Günnemann, "Adversarial attacks on graph neural networks via meta learning," in International Conference on Learning Representations (ICLR), 2019.
  36. A. Bojchevski and S. Günnemann, "Adversarial attacks on node embeddings via graph poisoning," in International Conference on Machine Learning (ICML), 2019, pp. 695-704.
  37. Z. Gyöngyi and H. Garcia-Molina, "Web spam taxonomy," in Inter- national Workshop on Adversarial Information Retrieval on the Web (AIRWeb), 2005.
  38. --, "Link spam alliances," in International Conference on Very Large Data Bases (VLDB), 2005, pp. 517-528.
  39. Z. Gyöngyi, H. Garcia-Molina, and J. O. Pedersen, "Combating web spam with TrustRank," in International Conference on Very Large Data Bases (VLDB), 2004, pp. 576-587.
  40. D. E. Denning, "A lattice model of secure information flow," Com- munications of the ACM, vol. 19, no. 5, pp. 236-243, 1976.
  41. D. Volpano, C. Irvine, and G. Smith, "A sound type system for secure flow analysis," Journal of Computer Security, vol. 4, no. 2-3, pp. 167- 188, 1996.
  42. A. Sabelfeld and A. C. Myers, "Language-based information-flow se- curity," IEEE Journal on Selected Areas in Communications, vol. 21, no. 1, pp. 5-19, 2003.
  43. A. C. Myers and B. Liskov, "A decentralized model for information flow control," in ACM Symposium on Operating Systems Principles (SOSP), 1997, pp. 129-142.
  44. N. Zeldovich, S. Boyd-Wickizer, E. Kohler, and D. Mazières, "Mak- ing information flow explicit in HiStar," in USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2006, pp. 263-278.
  45. W. Enck, P. Gilbert, B.-G. Chun, L. P. Cox, J. Jung, P. D. McDaniel, and A. Sheth, "TaintDroid: An information-flow tracking system for realtime privacy monitoring on smartphones," in USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2010, pp. 393-407.
  46. P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W.-T. Yih, T. Rocktäschel, S. Riedel, and D. Kiela, "Retrieval-augmented generation for knowledge-intensive NLP tasks," in Advances in Neural Information Processing Systems, 2020, arXiv:2005.11401. [Online]. Available: https://arxiv.org/abs/2005.11401 · arXiv
  47. D. Edge, H. Trinh, N. Cheng, J. Bradley, A. Chao, A. Mody, S. Truitt, D. Metropolitansky, R. O. Ness, and J. Larson, "From local to global: A Graph RAG approach to query-focused summarization," 2024, arXiv:2404.16130. [Online]. Available: https: //arxiv.org/abs/2404.16130 · arXiv
  48. Z. Guo, L. Xia, Y. Yu, T. Ao, and C. Huang, "LightRAG: Simple and fast retrieval-augmented generation," 2024, arXiv:2410.05779. [Online]. Available: https://arxiv.org/abs/2410.05779 · arXiv
  49. Z. Fountas, M. A. Benfeghoul, A. Oomerjee, F. Christopoulou, G. Lampouras, H. Bou-Ammar, and J. Wang, "Human-inspired episodic memory for infinite context LLMs," in International Conference on Learning Representations, 2025, arXiv:2407.09450. [Online]. Available: https://arxiv.org/abs/2407.09450 · arXiv

Cited by

Sorted by citations

Authors
Fei, Z., Fei, H., Wang, X., yang, Y., Gope, P., Sikdar, B., & Zhang, Y.
Affiliations
  • University of Technology Sydney (AU)
  • National University of Singapore (SG)
  • University of Sheffield (GB)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2026
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2606.12290
arXiv
2606.12290
OpenAlex
W7164421142
Cited by
0
References
1
Type
posted content
Language
en
Open access
Licence
Locations
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
Topics
  • Social Sciences › Sociology and Political Science › Access Control and Trust
  • Physical Sciences › Computer Science › Artificial Intelligence › Security and Verification in Computing
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
Keywords
information flow control, agent memory, top-k selection, personalized PageRank, re-ranking, document question answering

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review