Provenance defenses for agent graph memory are blind by construction

What is this?

On June 10, 2026, a paper titled Selection Integrity for LLM Graph Memory (arXiv:2606.12290, cs.CR) made a sharp claim about a defense pattern that has quietly become standard: as agent memory moves from flat document stores to graphs, teams add provenance defenses that check where retrieved records came from. The paper argues this entire class of defense is blind by construction — it can be defeated without forging, spoofing, or tampering with a single authenticated source.

The result matters because graph memory and memory poisoning are now central to agent security, and provenance/information-flow control (IFC) is the defense most people reach for. The finding says: against this specific channel, faithful IFC makes the byte-identical decision to having no defense at all.

How it works

The attack targets selection, not content. A long-term graph memory runs a global selection step (a ranker or retriever) over writable graph structure to decide which records reach the model’s context. Provenance defenses then check the provenance of the records the agent retrieves — and every retrieved record is legitimately authenticated.

The gap: an untrusted principal who can write structure — edges, nodes, links — does not need to inject a fake fact. The structural write changes which authenticated facts win the top-k selection, while the cited evidence stays fully authenticated. Because faithful IFC checks the provenance of what the reader actually uses (all of it authenticated), it permits the rerouted result exactly as it would permit the honest one.

Honest graph        →  selection  →  top-k = {authenticated fact A}  →  IFC: allow ✓
+ sourceless        →  selection  →  top-k = {authenticated fact B}  →  IFC: allow ✓
  structural write      (rerouted)     (still fully authenticated)       (same decision)

The paper characterizes exactly which selectors 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 — a sourceless write reroutes conserved random-walk mass. A content-fixed reranker cannot. Graphiti’s node-distance, which leans on structure even more than PageRank, stays immune. The predictor, the authors stress, is reallocatability, not reliance: how much structure a selector uses matters less than whether an untrusted write can reallocate ranking mass. They prove the immune case in general and the open (exploitable) case under a chokepoint condition they verify.

In the most consequential evaluation, a single no-source structural write silently misdirected 28 irreversible ledger transfers across 499 live actions in a real multi-session agent memory. Faithful IFC permitted every one.

Why it matters

This is an architectural blind spot, not a bug in one product. If you defend agent memory by checking the provenance of retrieved records — the natural reading of responsibility-attribution work on poisoned knowledge and of the broader long-term memory security literature — you may believe you have closed the door while the selection channel stays wide open. The impact is highest where the agent takes irreversible actions (payments, ledger writes, deletions) downstream of what memory surfaces, and where untrusted content can reach the graph’s structure (shared multi-session memory, collaborative knowledge graphs, agent-to-agent memory). The precondition — write access to structure — is exactly the condition multi-session and multi-tenant memory designs create.

Defenses

The paper’s own fix is the clearest mitigation, and it generalizes.

1. Recompute selection on the authenticated subgraph. Closing the channel forces any provenance defense to re-run the selection step over only the structure the reader is allowed to trust — not to check provenance after the fact. The authors’ AuthSelect does this at zero over-block and 2–3% latency, so the cost argument against it is weak.
2. Audit your selector for reallocatability. Ask whether an untrusted structural write can move an Ω(1) share of top-k membership. Personalized-PageRank-style selectors are exposed; content-fixed rerankers and node-distance selectors are not. Treat reallocatability — not how “structural” the selector feels — as the risk signal.
3. Gate structural writes the way you gate content. Most poisoning defenses scrutinize injected facts. Apply the same trust boundary to edges and links: who may add structure to shared memory, and is that structure attributable to a trusted principal?
4. Keep irreversible actions off raw memory selection. Where an agent can move money or delete data, require a confirmation or trusted re-derivation step between “memory said X” and the side effect — the lethal-trifecta logic applied to memory retrieval.

Status

Item	Reference	Date	Notes
Selection Integrity for LLM Graph Memory	arXiv:2606.12290v1	2026-06-10	Provenance/IFC defenses for graph memory blind to structural selection rewriting
Exposed selector	Paper §results	2026-06-10	Personalized PageRank — sourceless write reroutes random-walk mass
Immune selectors	Paper §results	2026-06-10	Content-fixed reranker; Graphiti node-distance
Proposed fix	AuthSelect	2026-06-10	Recompute selection on authenticated subgraph; 0 over-block, 2–3% latency

The takeaway is not “provenance defenses are useless” — it is that provenance of the retrieved record is the wrong checkpoint for graph memory. The decision that matters is selection, and selection has to be recomputed on trusted structure, or the rest of the defense is checking the right answer to the wrong question.