Selection Integrity for LLM Graph Memory: An Accumulability Criterion for Information-Flow-Blind Retrieval
Pith reviewed 2026-06-27 09:12 UTC · model grok-4.3
The pith
Untrusted writes to graph structure can redirect which authenticated facts an LLM memory retrieves, bypassing provenance checks.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
A selector admits an information-flow-blind channel precisely when its structural term can reallocate an Omega(1) share of top-k membership past a selected fact's margin; Personalized PageRank permits this because a sourceless write reroutes conserved random-walk mass, whereas a content-fixed reranker cannot and Graphiti's node-distance remains immune. Closing the channel requires any provenance defense to recompute selection on the authenticated subgraph, which authselect does at zero over-block and 2-3 percent latency.
What carries the argument
authselect, which enforces selection integrity by recomputing the global selection step exclusively over the authenticated subgraph rather than the full writable graph.
If this is right
- Personalized PageRank admits the channel because a sourceless write reroutes conserved random-walk mass.
- A content-fixed reranker cannot admit the channel.
- Graphiti's node-distance method, which relies on structure more than PageRank, stays immune.
- Any defense that recomputes selection on the authenticated subgraph closes the channel.
- Reallocatability, not reliance on structure, predicts whether a selector is exposed.
Where Pith is reading between the lines
- The same reallocatability test could be applied to other graph-memory substrates such as knowledge-graph-augmented retrieval or multi-agent shared state.
- If most deployed selectors turn out to be reallocatable, then provenance systems for agents will need to adopt authenticated-subgraph recomputation as a default.
- The chokepoint condition used to prove immunity for certain methods may generalize to other conservative flow measures beyond random walks.
Load-bearing premise
A long-term graph memory runs a global selection step over writable graph structure, so structure that an untrusted principal writes changes which authenticated facts are selected while the cited evidence stays fully authenticated.
What would settle it
Run the 499-action ledger-transfer trace once with the structural write present and once with authselect enabled; if the 28 misdirected transfers occur under provenance-only IFC but are blocked under authselect, the claim holds.
Figures
read the original 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 $\Omega(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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that provenance-based information-flow control defenses for LLM graph memory are blind by construction to attacks via untrusted structural writes, which can reallocate selection among authenticated facts without altering their provenance. It introduces an accumulability criterion based on reallocatability of top-k membership, proves that content-fixed rerankers and Graphiti node-distance are immune while Personalized PageRank is vulnerable, verifies a chokepoint condition for the open case, and shows that authselect (recomputing selection on the authenticated subgraph) closes the channel with zero over-block and 2-3% latency overhead. The central concrete instance is a no-source structural write that misdirects 28 irreversible ledger transfers over 499 actions, which IFC permits but authselect blocks.
Significance. If the central characterization and proofs hold, the result is significant: it identifies a structural blind spot in current IFC approaches for agent memory, distinguishes reallocatability from mere structural reliance as the predictor of vulnerability, supplies a general proof for the immune case plus a verifiable chokepoint condition, and demonstrates a practical, low-overhead mitigation (authselect) that preserves all authenticated facts while blocking the attack. The 28-transfer ledger example and cross-substrate validation add concrete falsifiability.
minor comments (3)
- [§3] §3 (or wherever the general proof appears): the statement that 'Graphiti's node-distance stays immune' would be clearer with an explicit reference to the node-distance formula used and how it satisfies the chokepoint condition.
- The 28-transfer ledger example is load-bearing for the practical claim; a short table or pseudocode snippet showing the exact structural write and the differing top-k sets before/after would improve verifiability without lengthening the paper.
- Notation for the accumulability criterion (Ω(1) share past margin) is introduced in the abstract but should be formalized with a numbered definition or equation in the main text for readers implementing the test.
Simulated Author's Rebuttal
We thank the referee for the careful reading and positive assessment of the work. The recommendation of minor revision is noted. No specific major comments were raised in the report, so we have no individual points requiring rebuttal or revision at this stage. We are prepared to address any minor editorial suggestions that may arise during the revision process.
Circularity Check
No significant circularity
full rationale
The paper's derivation begins from the observation that graph memory selectors operate over writable structure, then distinguishes reallocatability (ability to shift Ω(1) top-k mass) from mere structural dependence, proves immunity for content-fixed rerankers and Graphiti node-distance in general, and supplies a chokepoint condition for the remaining case. The authselect construction is introduced directly as the requirement to recompute selection on the authenticated subgraph; this follows from the preceding characterization without any fitted parameter, self-referential definition, or load-bearing self-citation. The ledger-transfer example is presented as a concrete instance of the identified channel rather than a statistically forced prediction. All load-bearing steps rest on explicit proofs and the stated assumptions rather than reduction to the paper's own inputs.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Long-term graph memory performs global selection over writable graph structure
invented entities (1)
-
accumulability criterion
no independent evidence
Forward citations
Cited by 1 Pith paper
-
Securing LLM-Agent Long-Term Memory Against Poisoning: Non-Malleable, Origin-Bound Authority with Machine-Checked Guarantees
Presents TMA-NM, a non-malleable origin-bound authority system for LLM-agent memory with TLA+ machine-checked separation theorems and benchmarks showing 0% attack success against direct and laundering poisoning while ...
Reference graph
Works this paper leans on
-
[1]
ReAct: Synergizing reasoning and acting in language models,
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
2023
-
[2]
Toolformer: Language models can teach themselves to use tools,
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,” inAdvances in Neural Information Processing Systems (NeurIPS), 2023
2023
-
[3]
Reflexion: Language agents with verbal reinforcement learning,
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
2023
-
[4]
Generative agents: Interactive simulacra of human behav- ior,
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,” inACM Symposium on User Interface Software and Technology (UIST), 2023
2023
-
[5]
MemoryGraft: Persis- tent compromise of LLM agents via poisoned experi- ence retrieval,
S. S. Srivastava and H. He, “MemoryGraft: Persis- tent compromise of LLM agents via poisoned experi- ence retrieval,” 2025, arXiv:2512.16962. [Online]. Available: https://arxiv.org/abs/2512.16962
arXiv 2025
-
[6]
A-MemGuard: A proactive defense framework for LLM-based agent memory,
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 2025
-
[7]
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 2026
-
[8]
A survey on the security of long-term memory in LLM agents: Toward mnemonic sovereignty,
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
Pith/arXiv arXiv 2026
-
[9]
HippoRAG: Neurobiologically inspired long-term memory for large language models,
B. J. Gutiérrez, Y . Shu, Y . Gu, M. Yasunaga, and Y . Su, “HippoRAG: Neurobiologically inspired long-term memory for large language models,” inAdvances in Neural Information Processing Systems, 2024, arXiv:2405.14831. [Online]. Available: https://arxiv.org/abs/2405.14831
arXiv 2024
-
[10]
From RAG to memory: Non-parametric continual learning for large language models,
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,” inInternational Conference on Machine Learning, 2025, arXiv:2502.14802. [Online]. Available: https://arxiv.org/abs/2502. 14802
Pith/arXiv arXiv 2025
-
[11]
Zep: A temporal knowledge graph architecture for agent memory,
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
Pith/arXiv arXiv 2025
-
[12]
Leveraging linguistic structure for open domain information extraction,
G. Angeli, M. J. J. Premkumar, and C. D. Manning, “Leveraging linguistic structure for open domain information extraction,” inAn- nual Meeting of the Association for Computational Linguistics (ACL), 2015, pp. 344–354
2015
-
[13]
Scaling personalized web search,
G. Jeh and J. Widom, “Scaling personalized web search,” inInterna- tional Conference on World Wide Web (WWW), 2003
2003
-
[14]
Fast random walk with restart and its applications,
H. Tong, C. Faloutsos, and J.-Y . Pan, “Fast random walk with restart and its applications,” inIEEE International Conference on Data Mining (ICDM), 2006, pp. 613–622
2006
-
[15]
Graphiti: Build real-time knowledge graphs for AI agents,
Zep, “Graphiti: Build real-time knowledge graphs for AI agents,” 2026, gitHub repository, accessed 2026-06-03. [Online]. Available: https://github.com/getzep/graphiti
2026
-
[16]
From Louvain to Leiden: Guaranteeing well-connected communities,
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 2019
-
[17]
Searching the graph,
Zep, “Searching the graph,” 2026, graphiti documentation, accessed 2026-06-03. [Online]. Available: https://help.getzep.com/graphiti/ working-with-data/searching
2026
-
[18]
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
Pith/arXiv arXiv 2023
-
[19]
W. Zou, R. Geng, B. Wang, and J. Jia, “PoisonedRAG: Knowledge corruption attacks to retrieval-augmented generation of large language models,” inUSENIX Security Symposium, 2025, arXiv:2402.07867. [Online]. Available: https://arxiv.org/abs/2402.07867
arXiv 2025
-
[20]
Poisoning retrieval corpora by injecting adversarial passages,
Z. Zhong, Z. Huang, A. Wettig, and D. Chen, “Poisoning retrieval corpora by injecting adversarial passages,” inConference on Empirical Methods in Natural Language Processing, 2023, arXiv:2310.19156. [Online]. Available: https://arxiv.org/abs/2310. 19156
arXiv 2023
-
[21]
AgentPoison: Red-teaming LLM agents via poisoning memory or knowledge bases,
Z. Chen, Z. Xiang, C. Xiao, D. Song, and B. Li, “AgentPoison: Red-teaming LLM agents via poisoning memory or knowledge bases,” inAdvances in Neural Information Processing Systems, 2024, arXiv:2407.12784. [Online]. Available: https://arxiv.org/abs/ 2407.12784
arXiv 2024
-
[22]
J. Liang, Y . Wang, C. Li, R. Zhu, T. Jiang, N. Gong, and T. Wang, “GraphRAG under fire,” inIEEE Symposium on Security and Privacy, 2026, arXiv:2501.14050. [Online]. Available: https://arxiv.org/abs/2501.14050
arXiv 2026
-
[23]
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 2025
-
[24]
Oracle poisoning: Corrupting knowledge graphs to weaponise AI agent reasoning,
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
Pith/arXiv arXiv 2026
-
[25]
Local graph partitioning using PageRank vectors,
R. Andersen, F. Chung, and K. Lang, “Local graph partitioning using PageRank vectors,” inIEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 475–486
2006
-
[26]
Unsupervised dense information retrieval with contrastive learning,
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
Pith/arXiv arXiv 2022
-
[27]
DeBERTa: Decoding-enhanced BERT with disentangled attention,
P. He, X. Liu, J. Gao, and W. Chen, “DeBERTa: Decoding-enhanced BERT with disentangled attention,” inInternational Conference on Learning Representations, 2021, arXiv:2006.03654. [Online]. Available: https://arxiv.org/abs/2006.03654
Pith/arXiv arXiv 2021
-
[28]
Evaluating very long-term conversational memory of LLM agents,
A. Maharana, D.-H. Lee, S. Tulyakov, M. Bansal, F. Barbieri, and Y . Fang, “Evaluating very long-term conversational memory of LLM agents,” inAnnual Meeting of the Association for Computational Linguistics, 2024, arXiv:2402.17753. [Online]. Available: https: //arxiv.org/abs/2402.17753
Pith/arXiv arXiv 2024
-
[29]
HotpotQA: A dataset for diverse, explainable multi-hop question answering,
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,” inConference on Empirical Methods in Natural Language Processing, 2018, arXiv:1809.09600. [Online]. Available: https://arxiv.org/abs/1809.09600
Pith/arXiv arXiv 2018
-
[30]
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
-
[31]
Constructing a multi-hop QA dataset for comprehensive evaluation of reasoning steps,
X. Ho, A.-K. Duong Nguyen, S. Sugawara, and A. Aizawa, “Constructing a multi-hop QA dataset for comprehensive evaluation of reasoning steps,” inInternational Conference on Computational Linguistics, 2020, arXiv:2011.01060. [Online]. Available: https: //arxiv.org/abs/2011.01060
Pith/arXiv arXiv 2020
-
[32]
LangGraph: Building stateful, multi-actor applications with LLMs,
LangChain, “LangGraph: Building stateful, multi-actor applications with LLMs,” 2024, software framework, accessed 2026-06-08. [Online]. Available: https://github.com/langchain-ai/langgraph
2024
-
[33]
Ignore previous prompt: Attack techniques for language models,
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
Pith/arXiv arXiv 2022
-
[34]
Formalizing and benchmarking prompt injection attacks and defenses,
Y . Liu, Y . Jia, R. Geng, J. Jia, and N. Z. Gong, “Formalizing and benchmarking prompt injection attacks and defenses,” inUSENIX Security Symposium, 2024
2024
-
[35]
InjecAgent: Benchmarking indirect prompt injections in tool-integrated large language model agents,
Q. Zhan, Z. Liang, Z. Ying, and D. Kang, “InjecAgent: Benchmarking indirect prompt injections in tool-integrated large language model agents,” inFindings of the Association for Computational Linguistics (ACL), 2024, pp. 10 471–10 506
2024
-
[36]
AgentDojo: A dynamic environment to evaluate attacks and defenses for LLM agents,
E. Debenedetti, J. Zhang, M. Balunovi ´c, L. Beurer-Kellner, M. Fis- cher, and F. Tramèr, “AgentDojo: A dynamic environment to evaluate attacks and defenses for LLM agents,” inAdvances in Neural Infor- mation Processing Systems (Datasets and Benchmarks Track), 2024, arXiv:2406.13352
Pith/arXiv arXiv 2024
-
[37]
The instruction hierarchy: Training LLMs to prioritize privileged instructions,
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
Pith/arXiv arXiv 2024
-
[38]
Adversarial attacks on neural networks for graph data,
D. Zügner, A. Akbarnejad, and S. Günnemann, “Adversarial attacks on neural networks for graph data,” inACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2018, pp. 2847–2856
2018
-
[39]
Adversarial attacks on graph neural networks via meta learning,
D. Zügner and S. Günnemann, “Adversarial attacks on graph neural networks via meta learning,” inInternational Conference on Learning Representations (ICLR), 2019
2019
-
[40]
Adversarial attacks on node embeddings via graph poisoning,
A. Bojchevski and S. Günnemann, “Adversarial attacks on node embeddings via graph poisoning,” inInternational Conference on Machine Learning (ICML), 2019, pp. 695–704
2019
-
[41]
Web spam taxonomy,
Z. Gyöngyi and H. Garcia-Molina, “Web spam taxonomy,” inInter- national Workshop on Adversarial Information Retrieval on the Web (AIRWeb), 2005
2005
-
[42]
Link spam alliances,
——, “Link spam alliances,” inInternational Conference on Very Large Data Bases (VLDB), 2005, pp. 517–528
2005
-
[43]
Combating web spam with TrustRank,
Z. Gyöngyi, H. Garcia-Molina, and J. O. Pedersen, “Combating web spam with TrustRank,” inInternational Conference on Very Large Data Bases (VLDB), 2004, pp. 576–587
2004
-
[44]
A lattice model of secure information flow,
D. E. Denning, “A lattice model of secure information flow,”Com- munications of the ACM, vol. 19, no. 5, pp. 236–243, 1976
1976
-
[45]
A sound type system for secure flow analysis,
D. V olpano, 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
1996
-
[46]
Language-based information-flow se- curity,
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
2003
-
[47]
A decentralized model for information flow control,
A. C. Myers and B. Liskov, “A decentralized model for information flow control,” inACM Symposium on Operating Systems Principles (SOSP), 1997, pp. 129–142
1997
-
[48]
Mak- ing information flow explicit in HiStar,
N. Zeldovich, S. Boyd-Wickizer, E. Kohler, and D. Mazières, “Mak- ing information flow explicit in HiStar,” inUSENIX Symposium on Operating Systems Design and Implementation (OSDI), 2006, pp. 263–278
2006
-
[49]
TaintDroid: An information-flow tracking system for realtime privacy monitoring on smartphones,
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,” inUSENIX Symposium on Operating Systems Design and Implementation (OSDI), 2010, pp. 393–407
2010
-
[50]
Retrieval-augmented generation for knowledge-intensive NLP tasks,
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,” inAdvances in Neural Information Processing Systems, 2020, arXiv:2005.11401. [Online]. Available: https://arxiv.org/abs/2005.11401
Pith/arXiv arXiv 2020
-
[51]
From local to global: A Graph RAG approach to query-focused summarization,
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
Pith/arXiv arXiv 2024
-
[52]
LightRAG: Simple and fast retrieval-augmented generation,
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
Pith/arXiv arXiv 2024
-
[53]
Human-inspired episodic memory for infinite context LLMs,
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,” inInternational Conference on Learning Representations, 2025, arXiv:2407.09450. [Online]. Available: https://arxiv.org/abs/2407.09450 Availability Our experimental harness, the knowledge-graph co...
arXiv 2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.