Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper critiques existing provenance defenses in graph-based agent memory systems, revealing that they are fundamentally ineffective due to their inability to account for structural writes by untrusted principals. The authors introduce a novel criterion, \authselect, which ensures that selection integrity is maintained by requiring provenance checks on the authenticated subgraph rather than relying solely on authenticated facts. Their findings demonstrate that \authselect can prevent significant misdirections in memory retrieval, showcasing its effectiveness in safeguarding against information flow attacks with minimal latency overhead.
Provenance defenses in graph memory systems are blind to structural manipulations, allowing critical misdirections that can lead to irreversible actions.
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.