From Agent Traces to Trust: A Survey of Evidence Tracing and Execution Provenance in LLM Agents

arXiv:2606.04990 · cs.CR, cs.AI · Submitted 2026-06-03 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "From Agent Traces to Trust: A Survey of Evidence Tracing and Execution Provenance in LLM Agents".

Jane: The paper was written by Yiqi Wang, Jiaqi Zhang, Zhangkai Wu, Taotao Cai, Zirui Liu et al. from Griffith University and Jiangsu University and University of Southern Queensland and Peking University and Great Bay University and Nanjing University and The University of Sydney and Southern University of Science and Technology.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Paper discussion segment 3: Tom: So, we’ve been discussing the core concepts introduced by "From Agent Traces to Trust: A Survey of Evidence Tracing and Execution Provenance in LLM Agents," and now we are shifting our focus to the practical implementation. We've established that simple logging is insufficient; we need a governance layer built into the evidence trail itself.

Jane: If the summary told us *what* we need, this segment tells us *how* to build it. We are talking about baking provenance directly into the core decision-making loop, making it an inherent part of the agent's operation rather than an add-on feature.

Meng: It sounds like we are moving from a reactive system—one that just records what happened after the fact—to a proactive one that validates actions before they take place.

Tom: Exactly, Meng. The paper suggests that adopting these improvements means moving beyond simple logging and adopting entire new frameworks centered on data governance and compliance standards.

Lu: To simplify this, are we talking about integrating a kind of mandatory internal checkpoint system? Something that checks the rules before the action is executed?

Jane: That's a very good way to put it, Lu. In simpler terms, the core message here is that we need to stop just recording *what* happened, and start enforcing *if* what happened was even permissible in the first place. This represents a massive jump in required sophistication for any system architect.

Lalam: From an industry standpoint, this suggests that accountability is becoming a prerequisite for deployment, not just a nice-to-have feature that can be added later on.

Tom: Jane and I were discussing how this leap requires entirely new engineering paradigms. We need to build systems that don't just record the path taken; they must prove the path was valid according to external regulations and internal policies.

Jane: Exactly. We’ve established that tracking the sequence of events and every piece of evidence is vital, but the next level—the improvement this paper highlights—is moving us from mere descriptive tracing to *prescriptive, policy-aware auditing*. It means the system doesn't just log that it used a database record; it must prove that using that record was compliant with all current rules.

Meng: This implies a constant, real-time cross-referencing process against a policy knowledge base—a very complex architectural undertaking.

Tom: From an engineering standpoint, this isn't something you can just bolt onto an agent; the entire decision-making loop has to be redesigned from the ground up. We are talking about building systems that actively check their own internal state transitions against a set of guardrails before they even execute.

Lu: Speaking of guardrails, this concept immediately brings up the privacy angle in a crucial way. If an agent needs to retrieve data, we can't just log every byte—that could expose sensitive information like private addresses or proprietary keys.

Jane: You hit on the most critical refinement here, Lu. The improvement is *selective tracing*. The system must be smart enough to know what data is restricted and only capture the absolute minimum metadata needed for the audit trail, nothing more than what's required to prove compliance.

Lalam: That selective approach is crucial because it allows for high transparency without sacrificing privacy, solving a major tension point in AI governance.

Tom: Furthermore, the paper tackles something called memory decay. A basic log just records what was seen; an advanced system must be able to detect when its foundational context is outdated or contradictory and then *invalidate* that old information mid-stream.

Jane: And crucially, it must also log the precise reason for that invalidation—the contradiction that forced the system to discard its own assumptions. This elevates the record from a simple history book to a legally defensible journal of reasoning.

Meng: For high-stakes areas like medicine or finance, this capability is absolutely everything because it proves due diligence when context shifts unexpectedly.

Tom: Ultimately, these improvements force us to build systems that are not just powerful, but provably accountable. This foundational understanding of rigorous governance sets us up perfectly to discuss how these architectural requirements translate into building entirely new validation pipelines for these complex systems.

Paper discussion segment 4: Tom: Building on the discussion of architectural improvements, we are now diving deeper into the advanced requirements outlined in "From Agent Traces to Trust: A Survey of Evidence Tracing and Execution Provenance in LLM Agents." We know that moving beyond simple logging is mandatory, but what does that actually look like under the hood?

Jane: To reiterate Jane's point from before, we need to move from mere descriptive tracing—just recording the steps—to *prescriptive, policy-aware auditing*. The depth here lies in making the system self-checking against defined legal or operational policies.

Lu: If I understand correctly, this suggests that every piece of evidence must carry not just its value, but also a compliance tag attached to it.

Meng: Precisely. It's about creating metadata tags that define not just *what* the data is, but *who* can use it and *under what conditions*. This adds layers of granular control that were previously impossible in LLM architectures.

Tom: And Jane elaborated on the selective tracing aspect, which addresses the sensitivity of data. It’s not enough to know that data exists; we must prove we only logged the non-sensitive aspects required for compliance.

Jane: Right, and this concept of selective tracing is what allows us to maintain a comprehensive audit trail without creating a massive privacy liability. We are capturing the minimum necessary metadata—the 'what' and 'why' of the access—but never the raw, sensitive data itself.

Lalam: This distinction between metadata logging and full data logging is really key for achieving adoption in highly regulated sectors, like finance or defense, where data leakage is catastrophic.

Meng: Beyond privacy, we also need to account for the dynamic nature of agent context. An agent's understanding changes as it interacts with the world, and that context can become outdated or contradictory over time.

Tom: That brings us back to memory decay—a concept that was perhaps less defined in earlier discussions but is crucial here. A basic log just records what was seen; an advanced system must be able to detect when its foundational context is outdated or contradictory and then *invalidate* that old information mid-stream.

Jane: And the crucial part, which elevates this discussion, is that it must log the precise reason for that invalidation—the specific contradiction or obsolescence that forced the system to discard its own assumptions. This turns a potential weakness into a verifiable strength.

Lu: So if an agent's initial assumption about

Paper discussion segment 3: ---: Paper discussion segment three ---

Tom: If we are to summarize this section on improvements, the core message is that simply adding a logging feature is completely insufficient; we need an entire governance layer baked into the system's architecture.

Jane: Exactly. We are moving from an observational record—a history book of actions—to a proactive, auditable journal of reasoning that constantly validates itself against established policies. The paper outlines specific mechanisms to achieve this level of rigor.

Meng: This shift means that the metric for success changes fundamentally. Previously, we might only ask: "Did the agent produce the correct output?" Now, we are forced to ask: "Did the agent operate *within* its authorized boundaries while producing that output?" The process is now inseparable from the result.

Lu: From a technical standpoint, one of the most complex improvements they highlight is handling contradictions or decay mid-task. An agent might start with Assumption A, but later encounter evidence supporting B. The system can’t just ignore the contradiction; it must log *why* it invalidated its initial assumption and what new guardrail forced that change.

Lalam: That points to the necessity of structured provenance records that aren't just descriptive. They need to be machine-readable and designed specifically for automated policy enforcement engines. If the evidence trail can't be consumed by a compliance tool, it provides zero value in regulated industries like finance or medicine.

Jane: So, we’re building a system that is self-correcting and self-proving. It doesn't just record what it saw; it records the *policy* that allowed it to proceed with what it saw.

Tom: This requires more than just logging inputs and outputs. We are talking about capturing the lineage of every piece of data used, from its source to how it was transformed, and flagging any potential conflict or policy violation at each step.

Meng: It’s a massive commitment to transparency that fundamentally changes the deployment conversation—it's no longer about trusting the output; it's about auditing the entire causal chain.

Lu: And that auditability must account for complexity, including when an agent needs to synthesize knowledge from multiple, potentially conflicting data domains simultaneously.

Lalam: This leads us directly into how we need to architect systems to handle not just single sources of truth, but entire networks of assumptions and dependencies within the trace itself.

Conclusion: Tom: So, in summary, this deep dive into "From Agent Traces to Trust" has shown us that accountability is no longer optional; it's the core requirement for deploying advanced AI.

Jane: Exactly. We started by talking about logging events, but we concluded that we need an entire structural framework—a governance layer—to prove the *permissibility* of every single step taken by an agent.

Meng: From a systemic viewpoint, this moves us into a new paradigm where trust is mathematically verifiable, not just assumed. It’s a massive maturation point for the field.

Lu: I think what this really solidifies is that the rigor required here elevates AI research to meet the standards of traditional engineering fields—it demands formal proof.

Lalam: And that proof capability fundamentally changes who can build these systems and, consequently, who will be able to deploy them safely in high-risk environments.

Jane: It’s a huge shift in focus for researchers and engineers alike: the system must prove its own compliance while it operates.

Tom: This entire discussion has shown us that the evidence trail must account for context decay, conflicting data, and adherence to constantly updated policies simultaneously.

Meng: It truly forces us to rethink what "intelligence" means in a practical sense—it’s intelligence coupled with rigorous, auditable self-awareness.

Lu: I suppose the biggest takeaway is that we are building AI systems that are designed not just to answer questions, but to withstand intense regulatory scrutiny years down the line.

Lalam: Ultimately, this work shows us how to build a verifiable chain of custody for knowledge itself—a necessary step for widespread industry adoption.

Jane: And so, as we wrap up our discussion on "From Agent Traces to Trust: A Survey of Evidence Tracing and Execution Provenance in LLM Agents," it’s clear that provenance is the essential bedrock requirement moving forward.

Tom: It’s been a truly fascinating deep dive, Jane. With this foundation laid out, I think we're perfectly set up to tackle something equally complex next time: the implications of these systems on international data sovereignty laws.

Griffith University · Jiangsu University · University of Southern Queensland · Peking University · Great Bay University · Nanjing University · The University of Sydney · Southern University of Science and Technology

cs.CR, cs.AI

Submitted: 2026-06-03

Updated: 2026-09-10

Code: https://github.com/OpenLineage/OpenLineage

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 88/100

The gist: This survey paper addresses the "process-level accountability gap" emerging in Large Language Model (LLM)-based agents.

Key concepts

Prescriptive, Policy-Aware Auditing
Instead of just recording what happened, this approach involves making systems self-check against legal or operational policies. The system must prove that every action taken was permissible according to specific rules, moving from mere descriptive tracing to active enforcement of compliance standards during operation.
Selective Tracing
This technique addresses privacy concerns by capturing only the minimum necessary metadata required for an audit trail. Rather than logging raw, sensitive data like private addresses, the system logs the "what" and "why" of data access to prove compliance without creating privacy liabilities.
Memory Decay
This involves an agent's ability to detect when its foundational context or assumptions have become outdated or contradictory. An advanced system must invalidate this old information mid-stream and log the precise reason for the invalidation, creating a verifiable record of the agent's reasoning process.

Terminology

Summary

This survey paper addresses the process-level accountability gap emerging in Large Language Model (LLM)-based agents. As these systems evolve from passive text generators into autonomous agents capable of planning, tool use, and multi-agent collaboration, their behavior becomes increasingly difficult to verify, debug, and audit. The authors argue that evaluating agents solely by final-answer correctness reveals nothing about how an output was produced, necessitating a shift toward evidence tracing and execution provenance to ensure trustworthy AI.

The provenance framework

The authors propose a unified framework that moves beyond simple agent traces to provide a process-level accountability layer. They distinguish between two core concepts: execution provenance and evidence tracing. Execution provenance is defined as the full typed graph of an agent execution, which models the complex connections among retrieved evidence, tool outputs, memory items, observations, intermediate claims, actions, and final answers. Evidence tracing is described as the projection [of this provenance structure] onto evidence-support relations, specifically explaining which evidence supports which claims, decisions, or actions. By connecting semantic support with procedural execution, this framework allows for a complete view of how an agent's reasoning and actions are shaped by its environment and history.

A six-dimensional taxonomy

To provide a compact vocabulary for comparing provenance-aware agent work, the paper introduces a taxonomy organized along six dimensions:

  • Trace sources, such as reasoning, retrieval, tool use, memory, and multi-agent communication.

  • Evidence and execution units, distinguishing between semantic objects (e.g., documents, claims, and policies) and procedural objects (e.g., tool invocations, reasoning steps, and memory operations).

  • Provenance relations, including typed links like SUPPORT, DEPEND-ON, CONTRADICT, INVALIDATE, TRIGGER, and UPDATE.

  • Tracing granularity and timing, ranging from token-level to run-level and from pre-execution to post-hoc.

  • Representation forms, such as structured logs, execution graphs, and provenance graphs.

  • Trust functions, which are the downstream purposes served by provenance, including verification, attribution, debugging, safety enforcement, audit, and recovery.

Key research threads

The survey categorizes existing research into seven main threads that address the complexities of agentic workflows. These include:

  1. Provenance representation and evidence attribution.

  2. Tool-use provenance, which examines whether tool calls are justified and how indirect prompt injection can contaminate tool contexts.

  3. Runtime guardrails, designed to prevent untrusted or unauthorized influence from reaching sensitive actions.

  4. Provenance-bearing memory, which treats memory items as evidence-bearing objects that must maintain source lineage and temporal validity.

  5. Observability and failure diagnosis, which focus on localizing responsible steps or error modes within long, complex executions.

Current gaps and open challenges

The authors identify a critical fragmentation in current evaluation methods, noting that existing benchmarks often evaluate isolated components rather than the entire agentic chain. To move toward full-stack provenance, the paper outlines several open challenges:

  • The need for unified and interoperable trace schemas that connect operational logs with semantic evidence.

  • The development of semantic provenance to track dependencies across transformations like summarization or paraphrasing.

  • The creation of recovery-oriented evaluation to determine if provenance can help a system repair itself through rollback or compensation.

  • The establishment of privacy-aware audit infrastructure to manage the risk that provenance traces themselves may contain sensitive user data or credentials.

Improvements for AI systems

1. Implementation of Provenance-Aware Runtime Guardrails

  • What the improved system can do: Instead of performing simple input/output filtering, the system will perform real-time source-to-sink influence analysis. It will track the lineage of every tool argument; if a sensitive parameter (e.g., a database query string, a file path, or an email recipient) is derived from an untrusted or unverified source (such as an external webpage or a third-party API response), the system will automatically block the execution, trigger a human-in-the-loop verification, or enforce strict parameter constraints to prevent indirect prompt injection and unauthorized state changes.

2. Transition to Provenance-Bearing Memory Architectures

  • What the improved system can do: The system will move away from opaque vector databases toward a structured memory graph where every stored item is an evidence unit linked to its origin (e.g., user instruction, tool output, or observation). This enables the system to perform automatic selective invalidation: when new evidence contradicts a stored memory, the system will use the provenance graph to identify and roll back all downstream claims, tool calls, and subsequent memory updates that were influenced by that stale or incorrect information, preventing long-horizon error propagation.

3. Deployment of Semantic Taint Tracking for Multi-Step Reasoning

  • What the improved system can do: The system will implement a mechanism to track semantic influence across transformations. When an agent summarizes a document or synthesizes multiple sources, the system will maintain a semantic taint link between the raw evidence and the resulting intermediate claim. This allows the system to detect if a later, seemingly safe action is actually being driven by the tainted logic of a previously processed adversarial instruction, even if the text has been heavily paraphrased or summarized.

4. Integration of Recovery-Oriented Execution (ROE) via Provenance Graphs

  • What the improved system can do: Upon detecting a failure (e.g., a tool error, a hallucination, or a policy violation), the system will move beyond simple retry loops. Using the execution provenance graph, it will perform surgical recovery: it will isolate the specific faulty execution unit, quarantine the contaminating evidence, roll back only the specific external state changes caused by that step, and re-run the reasoning process using a corrected dependency path.

5. Adoption of Process-Level Accountability Benchmarking

  • What the improved system can do: During the training and evaluation phases, the system will be optimized for trace completeness and dependency coverage rather than just final-answer accuracy. This ensures that the model is penalized not just for being wrong, but for being right for the wrong reasons—such as providing a correct answer that lacks a verifiable evidence-support link or a tool call that lacks a justified reasoning step, thereby ensuring the agent is inherently auditable and trustworthy.

Sources

Related papers