PaperlayerView exact revision on arXiv

Source-linked AI summary

MemMark: State-Evolution Attribution Watermarking for Agent Long-Term Memory Systems

Haobo Zhang, Xutao Mao, Guangyuan Dong, Ziwei Li, Xuanbo Su, Kaijie Chen, Jing Yang, Zheng Lin

arXiv:2605.25002v4cs.CR

TL;DR

Memory-backed agents need attribution that survives untrusted snapshots after logs and metadata are lost or manipulated. MEMMARK embeds a keyed signal in utility-preserving memory-evolution decisions and authenticates it with replayable evidence. Across two backends and six model–backend settings, it preserves utility while enabling snapshot-only payload recovery, though broader lifecycle and adaptive-attack coverage remains open.

  • Problem

    Snapshot-only forensics lacks trusted write-time traces, while mutable ownership and provenance fields can be rewritten by an attacker.

  • Method

    MEMMARK selects among semantically admissible memory-write candidates with keyed, distribution-preserving sampling and records authenticated evidence for replay across verification regimes.

  • Results

    MEMMARK retains 99.6% of unwatermarked Overall F1, exposes 1.16, 1.14, and 1.26 bits of mean carrier entropy, and recovers the full 40-bit payload in R3.

  • Takeaways & Limitations

    Durable memory attribution can survive beyond visible actions, final text, and trusted metadata when tied to utility-preserving state choices and authenticated reveal evidence.

  • Takeaways & Limitations

    Evaluation covers two memory backends and representative attacks, not broader lifecycle operations or exhaustive adaptive evidence-removal attempts.

Abstract

from arXiv · show

Memory-backed agents need provenance that can survive leaked or migrated snapshots, where logs, visible outputs, and trusted metadata may be absent. We propose MemMark, a state-evolution attribution watermark that embeds an owner-controlled signal into latent memory-write decisions. At each internal LLM call, MemMark samples among admissible candidates using keyed, distribution-preserving selection, and records cryptographic commitments with signed session anchors and reveal evidence. This makes attribution depend on reproducible backend behavior rather than mutable provenance fields. Across A-Mem and Graphiti on LoCoMo, with three LLM backbones, MemMark preserves memory utility: Overall F1 retains 99.6% of the unwatermarked baseline, while BLEU-1 changes by +0.2%. It also provides usable carrier capacity, with 1.16, 1.14, and 1.26 bits of mean entropy for update-target, link-target, and semantic-realization decisions. In the snapshot-only R3 setting, MemMark recovers the full 40-bit payload from final snapshots, while wrong-key verification remains near chance. Under nine memory-lifecycle attacks, verification distinguishes tampering, evidence deletion, and partial payload recovery. These results show that robust snapshot-only attribution is feasible for long-term agent memory without surviving traces, trusted metadata, or utility-degrading.

1 Introduction

MEMMARK addresses attribution when memory snapshots outlive trusted logs and mutable provenance fields. It embeds signals in utility-preserving memory-evolution choices and reports near-baseline utility, carrier capacity, and snapshot-only recovery.

  • Persistent agents make memory a security boundary because state survives across interactions and undergoes extraction, updating, consolidation, linking, and deletion.
  • Snapshot-only forensics assumes logs and write-time traces may be absent, corrupted, or controlled by an attacker who can rewrite ownership and provenance fields.
  • MEMMARK embeds attribution in latent choices over update targets, link targets, and semantically equivalent realizations rather than mutable metadata.
  • R3 recovers the full 40-bit payload, compared with no recovery for signed-metadata-only and 15% wrong-key recovery.
  • 99.6% of unwatermarked Overall F1 is retained, while BLEU changes by +0.2%.
  • Mean carrier entropies are 1.16, 1.14, and 1.26 bits for update-target, link-target, and semantic-realization decisions.

2 Related Work

Related work spans persistent-memory systems, memory-writing benchmarks, provenance metadata, and watermarks for text, data, graphs, and agent behavior. MEMMARK targets the memory-evolution channel when conventional evidence may be unavailable or untrusted.

  • Persistent-memory systems maintain note networks, temporal graphs, or structured memory objects, while benchmarks test recall, updates, temporal reasoning, and incremental state.
  • Memory-writing research treats admission, update, and curation as explicit decision layers, providing the layer MEMMARK watermarks.
  • Figure 1 situates MEMMARK as a pipeline that intercepts memory writes, selects keyed candidates, and preserves evidence for multiple verification regimes.
  • Existing provenance systems attach source anchors, versions, or lifecycle metadata, but metadata helps under trusted storage rather than adversarial snapshot control.

3 Problem Formulation

The formulation models memory writing as a sequence of semantically admissible, backend-dependent decisions and embeds provenance through keyed sampling while preserving the native write path. It defines full-log, partial-log, and snapshot-only verification under utility and attribution objectives.

  • 3.1 Preliminaries and Notation: At turn t, a backend maps event e_t and snapshot M_t to M_t+1 through latent, semantically admissible state-evolution choices.
  • 3.1 Preliminaries and Notation: The candidate set C_t, preference distribution π_t, and reconstructible context ctx_t define each memory-evolution decision.
  • 3.2 Memory-Evolution Channel and Distribution-Preserving Coding: MEMMARK replaces native sampling with a distribution-preserving encoder using reproducible per-decision randomness and context-derived keyed nonces.
  • 3.1 Preliminaries and Notation: The watermark modifies only the selected candidate, while APPLY_SELECTED remains on the native backend path.
  • 3.3 Threat Model: Verification covers R1 full external logs, R2 partial surviving commitments, and R3 snapshot-only evidence with an in-record sidecar.
  • 3.3 Threat Model: Poisoning and compaction are modeled as a surviving decision subset, while anchored commitments prevent forged openings without the secret key.
  • 3.3 Threat Model: The carrier taxonomy is backend-specific in realization but backend-invariant at the sampler interface, which reads only C, π, and ctx.
  • 3.4 Objectives: Utility preservation requires downstream quality retention, motivating semantically equivalent candidates; robust attribution should improve as surviving decisions increase.

4 MemMark

MEMMARK exposes backend decision freedom, converts it into discrete candidate distributions, and applies keyed distribution-preserving sampling before native commits. Cryptographic commitments, Merkle evidence, and inclusion proofs support replay and tamper-evident verification.

  • Carrier taxonomy: The pipeline exposes update-target, link-target, and semantic-realization carriers while leaving the native commit path unchanged.
  • Backend adapter: Three adapter hooks expose choices, score candidates, and commit the selected candidate across structurally different backends.
  • Decision interception and elicitation: MEMMARK elicits K plausible answers with preference weights, producing a discrete candidate set and normalized distribution for keyed replay.
  • Keyed distribution-preserving sampling: The keyed sampler consumes candidates, preferences, and context, returns a selected candidate and embedded-bit count, and preserves the marginal distribution.
  • Sampler properties: Backend invariance means the keyed pick depends on the candidate distribution and secret key, not on the backend that produced the candidates.
  • Cryptographic audit trace: MEMMARK records a cryptographic trace, with per-decision commitments and a Merkle root sealed in a signed anchor for tamper evidence.
  • Cryptographic audit trace: Per-leaf inclusion proofs let surviving records be checked against the anchored root without rebuilding the full log.

5 Experiments

Experiments evaluate MEMMARK's utility, carrier capacity, snapshot and partial-log verification, attack robustness, and memory integrity across A-MEM, GRAPHITI, three backbones, and LoCoMo. MEMMARK preserves utility while providing recoverable attribution and diagnostic behavior under lifecycle attacks.

  • RQ1 — Utility Preservation: Across six model–backend settings, MEMMARK changes Overall F1 from 0.2816 to 0.2804, retaining 99.6% of the unwatermarked baseline.Average BLEU-1 changes from 0.3069 to 0.3077, improved by 0.2%.
  • RQ1 — Utility Preservation: The watermark remains in a comparable utility regime while moving attribution evidence from signed metadata into backend memory-evolution choices.Signed-metadata-only leaves utility largely unchanged but does not create a recoverable state-evolution signal.
  • RQ2 — Capacity: Mean per-decision entropies are 1.16, 1.14, and 1.26 bits for update-target, link-target, and semantic-realization decisions, respectively.Semantic realization has the highest-capacity carrier average.
  • RQ2 — Capacity: Carrier payload shares follow backend structure: GRAPHITI places 49%–75% of embedded bits on semantic realization across the three backbones.A-MEM's Qwen3.6-flash split is 10% update, 25% link, and 65% semantic, while its GLM-5 split is 28%, 32%, and 40%.
  • RQ3 — Snapshot-Only / Partial-Log Verification: R3 recovers the full 40-bit payload from the final snapshot, while signed-metadata-only recovers 0.00 and wrong-key recovery is 0.15.With keep ratios r = 0.1, 0.3, 0.5, 0.7, and 0.9, mean R2 recovery rises from 0.08 to 0.29, 0.51, 0.71, and 0.90.
  • RQ4 — Robustness: Under nine lifecycle attacks, non-removal attacks remain recoverable at mild strengths but diverge at strength 0.5, while removal attacks preserve authenticated records and produce Miss.Edits, compaction, and poisoning trigger ComF; pruning and deduplication keep Rec at 1.00.
  • RQ5 — Memory Integrity: MEMMARK preserves memory-integrity behavior: A-MEM retrieval recall retains 89.3% of the no-watermark baseline, while GRAPHITI retains 97.5%.A-MEM write failures change from 4 to 3, and Qwen semantic carriers account for 55.0% of A-MEM and 58.6% of GRAPHITI carrier decisions.

6 Conclusion

MEMMARK binds provenance to long-term memory state-evolution choices rather than mutable metadata. The results support durable attribution beyond visible actions, final text, and trusted metadata when utility-preserving choices and authenticated reveal evidence are available.

  • 6 Conclusion: MEMMARK binds provenance to backend write, update, linking, and retention choices in the state-evolution layer of long-term agent memory.Its evidence is carried by utility-preserving state choices and authenticated reveal evidence.

7 Limitations

The evaluation is limited to two memory backends and the LoCoMo benchmark, while broader lifecycle and adaptive-attack settings remain future work. Deployment also depends on reliable key, evidence, and serialization management, and verification does not establish memory truth or safety.

  • Scope limitations: MEMMARK is evaluated on two memory backends and one auditable benchmark, leaving broader deployment settings to future work.Longer lifecycles, backend-specific compaction, migration, and periodic summarization may introduce new carriers and drift.
  • Attack coverage: The attack study covers representative edits, deletions, and poisoning but does not exhaust adaptive evidence-removal attacks that preserve utility.The authors identify distinguishing benign lifecycle changes from targeted tampering as a next step.
  • Scope limitations: The study uses ten fixed LoCoMo conversations across main model–backend configurations, limiting evaluation breadth.The fixed protocol enables like-for-like comparisons across methods, backends, and backbones.
  • Operational risks: Verification depends on secret keys, canonicalized reveal evidence, cryptographic audit material, and consistent serialization across systems.Leaked keys, mishandled sidecars, or inconsistent canonicalization may make verification unreliable.
  • Interpretation boundary: Successful watermark verification shows consistency with the keyed sampler and audit trace, not that the memory content is true or safe.This limits the claim that attribution evidence can support about the underlying memory.

B.2 Proof of Lemma 2

Lemma 2 establishes that MemMark’s keyed sampling remains distribution-preserving across multiple internal calls and is invariant to the backend once decisions are exposed through the common adapter representation.

  • Call separation: Distinct context fields domain-separate the m internal calls triggered by one memory event.Each context includes the round index, dialogue identifiers, prompt hash, and previous commitment, making collisions negligible.
  • Keyed sampling: Adaptive later contexts remain secure because PRF outputs on distinct inputs are computationally indistinguishable from independent uniform draws.This supports applying the single-decision distribution-preservation result at every call.
  • Capacity: Total cascade capacity is Bt = Pm j=1 E[Bt,j], because independent PRF outputs yield a product-form joint distribution.The capacity expression follows by linearity of expectation over the decisions.
  • Cascade guarantee: Every stage preserves its marginal distribution, so additional calls add evidence and capacity without accumulating systematic sampling bias.This is the main multi-call consequence of the lemma.
  • Backend abstraction: The sampler uses only the emitted decision tuple and watermark secret, not backend-specific representations such as notes, entities, edges, or surface realizations.The adapter therefore abstracts over the backend’s native memory-write structures.
  • Backend invariance: Backends exposing the same (Ct, πt, ctxt) receive the same marginal law and replay rule, without implying identical native candidate distributions.The guarantee applies after each backend reduces its choice to the common adapter representation.

C Metrics

The metrics and baselines organize evaluation around utility, capacity, verification, tamper detection, and integrity, while sensitivity analysis examines candidate count and enumeration temperature as key trade-off controls.

  • Metric organization: Evaluation metrics are grouped by five research questions: utility, capacity, snapshot-only verification, tamper detection, and memory integrity.The metrics also report carrier-level decomposition for update target, link target, and semantic realization where relevant.
  • Baselines: No-WM is the unwatermarked execution path and serves as the utility reference for RQ1 and RQ5.The backend, agent harness, and evaluation pipeline match MEMMARK runs; only attribution logic is removed.
  • Baselines: S.M.-Only retains signed metadata but removes keyed candidate selection, testing whether attribution can be explained by explicit metadata alone.In R3 it can validate a signed sidecar but cannot recover writer-specific state-evolution bits.
  • Baselines: Ran. replaces keyed sampling with random selection among the same admissible candidates, isolating effects of enumeration from secret-keyed selection.Because its choices are not reproducible from K, it is not expected to verify as MEMMARK evidence.
  • Baselines: KGMARK is evaluated only for GRAPHITI because its graph-native edge operations are not exposed by A-MEM.It provides a narrower graph-specialized comparison against the backend-invariant MEMMARK design.
  • Sensitivity analysis: The sensitivity study varies K ∈ {2, 4, 8} and Tenum ∈ {0.5, 0.7, 1.0} around the default K=4, Tenum=0.7.Candidate count is expected to affect capacity and wrong-key chance, while enumeration temperature affects diversity–utility balance.
  • Sensitivity analysis: The default setting is a stable middle point: larger K increases capacity and wrong-key separation but makes utility deltas more negative.Lower K reduces capacity and moves wrong-key recovery toward chance; temperature produces a softer version of the same trade-off.

F Overall and Per-Conversation Experimental Results

Across three LLMs and two memory backends, MEMMARK remains in the same overall utility regime as unwatermarked systems. Per-conversation results show modest backend-dependent variation rather than a single brittle failure mode, while verification remains stable and key-specific.

  • Per-conversation results: The appendix conversation-level table is diagnostic rather than conceptual and indicates that aggregate trends are not driven by a single conversation outlier.It reports all 10 LoCoMo conversations for Qwen3.6-flash and the A-MEM backend.
  • Overall results: MEMMARK tracks the main Overall F1 utility curve across three LLMs and two memory backends rather than collapsing performance.The backend effect is larger than the watermark effect, with A-MEM generally more stable and GRAPHITI showing a somewhat stronger drop in harder settings.
  • Per-conversation results: A-MEM shows small per-conversation F1 deltas centered near zero, with a mean gap of +0.006.GRAPHITI is more variable and sensitive to conversation-specific structure, with a mean gap of −0.038 in the Qwen3.6-flash diagnostic.
  • Attack diagnostics: Robustness evaluation covers nine memory-lifecycle attacks spanning content tampering and record removal.Content mutations are intended to surface as commitment_fail, while removal attacks expose missing authenticated evidence.

G.1 Graphiti Backend Robustness

On GRAPHITI, attack-specific verification preserves key-specific recovery while distinguishing content tampering, synthesis, poisoning, and evidence removal. Recovery and wrong-key separation vary by attack family and strength, revealing backend-specific sensitivity.

  • Content attacks: Content attacks on GRAPHITI achieve average Rec values of 0.911, 0.694, and 0.489 at strengths 0.1, 0.3, and 0.5.Their corresponding average ∆WK values are +0.629, +0.412, and +0.207.
  • Cross-backend comparison: The GRAPHITI backend shows the same qualitative robustness pattern as A-MEM but with backend-specific sensitivity.The reported breakdown uses Rec, Mode, and ∆WK to compare recovery and key-specific attribution separation.
  • Synthesis and poisoning: At strength 0.5, synthesis is the most damaging case, with mean Rec 0.462 and ∆WK +0.180.Poisoning remains more recoverable because it is additive, with mean Rec 0.705 and ∆WK +0.423.
  • Evaluation structure: Table 10 reports attack family, verifier mode, post-attack bit recovery, and wrong-key separation for GRAPHITI.∆WK is defined as Rec − WrongKey against the model’s wrong-key R3 baseline across strengths s ∈ {0.1, 0.3, 0.5}.
  • Removal attacks: Removal attacks preserve Rec 1.00 over surviving records and retain an average wrong-key margin of ∆WK = +0.718.Their Miss mode identifies the deletion-style lifecycle mutation while authenticated surviving records remain replayable.
Loading 2605.25002v4…