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

• URL: http://arxiv.org/abs/2606.12290v1
• Date: Wed, 10 Jun 2026 16:26:46 GMT
• Title: Selection Integrity for LLM Graph Memory: An Accumulability Criterion for Information-Flow-Blind Retrieval
• Abstract summary: We show that the entire class of provenance defense is blind by construction.<n>A long-term graph memory runs a global selection step over writable graph structure.<n>We prove the immune case in general and the open case under a chokepoint condition we verify.
• Score: 16.858503871105135
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• You've Got a BUD in Me: Authenticated Reads from Per-Block Write Logs [41.99844472131922]
  We show how validators can support historical membership and exclusion proofs by authenticating each block's writes instead.<n>A Block Update Digest commits a write log whose predecessor pointers link successive modifications of each key.<n>A SuperBUD summarizes last writes over a window; an exponential hierarchy turns long unchanged intervals into short proofs.
  arXiv  Detail & Related papers  (2026-09-10T08:46:09Z)
• Privacy-Preserving Topology-Guided Safety for LLM-Based Multi-Agent Systems via Federated Graph Learning [67.04448659688579]
  FGLGuard cuts AgentDojo's ground-success rate by 43% at near-unguarded utility, zero API cost, and negligible capability loss.<n>Federation is not optional: off-the-shelf transfer collapses under distribution shift.<n>Live FGLGuard cuts AgentDojo's ground-success rate by 43% at near-unguarded utility, zero API cost, and negligible capability loss.
  arXiv  Detail & Related papers  (2026-09-02T07:57:12Z)
• Agent Zero Memory: Provenance-Aware Long-Term Memory for LLM Agents [3.6666917625778193]
  Agent Zero Memory is a provenance-aware long-term memory system.<n>It distils a user's conversations, files, and connected sources into three parallel memory systems.
  arXiv  Detail & Related papers  (2026-08-30T06:55:59Z)
• Progressive Disclosure for LLM-Maintained Wiki Knowledge Bases: a Preregistered Ablation [0.0]
  We run a preregistered ablation in which four versions of the corpus differ only in how the agent reaches the content.<n>We grade answers blind against verified gold references with a cross-family judge.<n>The study doubles as a case study in evaluation validity, applying threat-to-validity discipline to the tooling that produced it.
  arXiv  Detail & Related papers  (2026-07-06T01:03:27Z)
• Securing LLM-Agent Long-Term Memory Against Poisoning: Non-Malleable, Origin-Bound Authority with Machine-Checked Guarantees [0.0]
  LLM agents increasingly rely on persistent long-term memory, which creates a critical vulnerability that we study here: memory poisoning.<n>An adversary can store untrusted content in one session that later steers a consequential action, such as a payment, a setting change, or data exfiltration.<n>Existing defenses base a memory item's authority to act on either its content (detection or trust-scoring) or its derivation history (lineage)<n>An attacker can launder an untrusted origin through three channels specific to LLM agents: the agent's own summarization, a trusted-tool echo, and manufactured corroboration
  arXiv  Detail & Related papers  (2026-06-23T08:57:50Z)
• Scaling Self-Evolving Agents via Parametric Memory [69.96398842169002]
  Existing memory-augmented LLM agents store past experience exclusively in prompt space.<n>We introduce textttTMEM, a self-evolving parametric memory framework.<n>textttTMEM consistently outperforms summary-based and retrieval-based baselines across different model scales.
  arXiv  Detail & Related papers  (2026-06-03T07:18:31Z)
• MemMark: State-Evolution Attribution Watermarking for Agent Long-Term Memory Systems [13.133650395551507]
  Memory-backed agents need provenance that can survive leaked or migrated snapshots.<n>MemMark embeds an owner-controlled signal into latent memory-write decisions.<n>MemMark is feasible for long-term agent memory without surviving traces, trusted metadata, or utility-degrading.
  arXiv  Detail & Related papers  (2026-05-24T11:04:35Z)
• GraphIP-Bench: How Hard Is It to Steal a Graph Neural Network, and Can We Stop It? [17.503523992356044]
  Graph neural networks (GNNs) deployed as cloud services can be emphstolen through emphmodel-extraction attacks.<n>We introduce emphGraphIP-Bench, a unified benchmark which evaluates both sides under a single black-box protocol.
  arXiv  Detail & Related papers  (2026-05-12T23:49:45Z)
• PRISM: : Planning and Reasoning with Intent in Simulated Embodied Environments [59.07829883257003]
  Built on five multi-room apartments, PRISM structures 300 human-verified tasks into three capability tiers.<n>PRISM exposes an agent-agnostic executable action API that allows arbitrary agents to be evaluated end-to-end.
  arXiv  Detail & Related papers  (2026-05-12T04:59:47Z)
• MemQ: Integrating Q-Learning into Self-Evolving Memory Agents over Provenance DAGs [47.66730296440261]
  We introduce MemQ, which propagates credit backward through a provenance DAG that records which memories were retrieved when each new memory was created.<n>Across six benchmarks, MemQ achieves the highest success rate on all six in generalization evaluation and runtime learning.<n>We further study how $$ and $$ interact with the EC-MDP structure, providing principled guidance for parameter selection and future research.
  arXiv  Detail & Related papers  (2026-05-08T18:30:24Z)
• AEL: Agent Evolving Learning for Open-Ended Environments [43.56685432981852]
  We introduce emphAgent Evolving Learning (ael), a two-timescale framework that addresses this obstacle.<n>ael achieves a Sharpe ratio of 2.13$pm$0.47, outperforming five published self-improving methods.<n>This demonstrates that the bottleneck in agent self-improvement is emphself-diagnosing how to use experience rather than adding architectural complexity.
  arXiv  Detail & Related papers  (2026-04-23T14:29:25Z)
• Progressive Online Video Understanding with Evidence-Aligned Timing and Transparent Decisions [75.23170605943457]
  textbfmodel is a framework that decouples reasoning control from memory integration.<n>emphActive Thinking Decision Maker (ATDM) is a transparent reasoning controller that externalizes its decision process.<n>emphHierarchical Progressive Semantic Integration (HPSI) module acts as an efficient memory system.
  arXiv  Detail & Related papers  (2026-04-20T16:15:33Z)
• CLAUSE: Agentic Neuro-Symbolic Knowledge Graph Reasoning via Dynamic Learnable Context Engineering [47.77119771502664]
  We introduce CLAUSE, an agentic three-agent neuro-symbolic framework that treats context construction as a sequential decision process over knowledge graphs.<n> CLAUSE employs the proposed Lagrangian-Constrained Multi-Agent Proximal Policy Optimization (LC-MAPPO) algorithm to coordinate three agents: Subgraph Architect, Path Navigator, and Context Curator.<n>Across HotpotQA, MetaQA, and FactKG, CLAUSE yields higher EM@1 while reducing subgraph growth and end-to-end latency at equal or lower token budgets.
  arXiv  Detail & Related papers  (2025-09-25T11:43:08Z)
• Proof-Carrying Numbers (PCN): A Protocol for Trustworthy Numeric Answers from LLMs via Claim Verification [0.0]
  We propose textbfProof-Carrying Numbers (PCN), a presentation-layer protocol that enforces numeric fidelity through mechanical verification.<n>PCN is lightweight and model-agnostic, integrates seamlessly into existing applications, and can be extended with cryptographic commitments.
  arXiv  Detail & Related papers  (2025-09-08T17:20:16Z)
• On Immutable Memory Systems for Artificial Agents: A Blockchain-Indexed Automata-Theoretic Framework Using ECDH-Keyed Merkle Chains [0.0]
  We introduce the concept of the Merkle Automaton, a cryptographically anchored, deterministic computational framework.<n>Each agent transition, memory fragment, and reasoning step is committed within a Merkle structure rooted on-chain.<n>This architecture reframes memory not as a cache but as a ledger - one whose contents are enforced by protocol, bound by cryptography, and constrained by formal logic.
  arXiv  Detail & Related papers  (2025-06-16T08:43: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.