Every Step Was Authentic. The History Was Not.

Authentic records can still be assembled into a false history.

Semantic Behavioral Watermarking: Paraphrase-Robust and Forgery-Resistant Provenance for LLM Agents studies how to embed provenance in an agent’s high-level action choices so traces can survive tool renaming and observation rewriting. The proposed method substantially improves robustness over exact-symbol watermarking and uses keyed binning to reduce adaptive forgery to the false-positive floor at the paper’s primary operating point.

But the paper identifies an important boundary: when an adversary copies the victim agent’s own genuine steps, chained replay remains highly successful—0.76 to 0.98 across five tested models.

The continuity failure

The watermark can establish that an action is authentic in origin. It cannot, by itself, establish that the action occurred in the claimed transaction, sequence, time, or authorization context.

Record / authentic action fragment → provenance check / valid origin ✕→ Context / original sequence and transaction → Authority / claimed trajectory → Future Reconstruction.

Every component can be genuine while the assembled story is false.

Why provenance needs context binding

This is a different problem from fabricated logs. An institution may possess cryptographically or behaviorally credible records and still reconstruct an event incorrectly if those records can be replayed outside the context that gave them meaning.

The issue resembles evidence reconstruction more broadly. GovKM’s article The Incident Was Contained. Its Evidence Stayed Online. shows that cross-system traces can be incomplete or distributed. Semantic Behavioral Watermarking adds another dimension: even authentic traces need sequence and transaction lineage.

The GovKM interpretation

Provenance should bind an action to more than an actor or model identity. Consequential records should preserve transaction ID, preceding state, authorization reference, sequence position, effective time, tool identity, and resulting state. Otherwise an authentic fragment can be transplanted into a different narrative.

This matters directly to AIL design. A node asserting that an action occurred should not be considered complete because the action signature is genuine. The edges connecting that action to the authority, context, predecessor state, and resulting record are part of the evidence.

Continuity path: Source / agent action → Evidence / provenance-bearing step → Authority / actor and task authorization → Context / transaction and sequence → Decision → Action → Record / trajectory → Institutional Memory / reconstructed history → Future Reuse.

Source

Suxin Ji, Hungtao Wan, Shaoxuan Chen, and An Zhang, Semantic Behavioral Watermarking: Paraphrase-Robust and Forgery-Resistant Provenance for LLM Agents, arXiv:2610.08668, October 6, 2026. https://arxiv.org/abs/2610.08668

DOI: https://doi.org/10.48550/arXiv.2610.08668