PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yiqi Wang, Jiaqi Zhang, Taotao Cai, Zirui Liu, Qingqiang Sun, Zequn Sun, Zhangkai Wu, Manqing Dong, Mingkai Zheng, Xuefei Yin, Yanming Zhu

arXiv:2606.04990v4cs.CRcs.AI

TL;DR

LLM-agent autonomy makes final-answer accuracy insufficient for verifying evidence, tool decisions, memory influence, and failure origins. This survey unifies evidence tracing with execution provenance, develops a six-dimensional taxonomy, and reviews methods and evaluation needs; it concludes that the field remains fragmented and lacks fine-grained, semantic, cross-agent, memory, and adversarial tracing.

  • Problem

    Final-answer accuracy cannot explain how agent outputs were produced, which evidence supported claims, whether tools were justified, how memory influenced decisions, or where failures originated.

  • Method

    The survey defines execution provenance as a complete typed representation of an agent run and evidence tracing as its evidence-support projection, then reviews representations, tool use, memory, evaluation, and open challenges.

  • Results

    The review shows that the field remains fragmented, with limited fine-grained claim support, semantic influence tracking, memory lineage, cross-agent provenance propagation, and robust tracing under adversarial conditions.

  • Takeaways & Limitations

    Evidence tracing and execution provenance should become a first-class infrastructure layer for reliable, traceable, auditable, and recoverable LLM agents.

  • Takeaways & Limitations

    Fine-grained provenance improves verification, debugging, audit, and recovery but increases storage cost, privacy exposure, annotation burden, and system complexity.

Abstract

from arXiv · show

Large language model (LLM)-based agents are evolving from passive text generators into autonomous systems capable of planning, tool use, retrieval, memory access, environmental interaction, and multi-agent collaboration. These capabilities expand agent autonomy, but also make agent behavior harder to verify, debug, and audit. Final-answer accuracy alone cannot explain how an output was produced, which evidence supported each claim, whether tool calls were justified, how memory influenced later decisions, or where failures originated. This survey examines evidence tracing and execution provenance as foundations for process-level accountability in trustworthy LLM agents. We define execution provenance as the typed graph of an agent execution and evidence tracing as its projection onto evidence-support relations. This perspective connects retrieval grounding, claim support, tool-use safety, memory lineage, observability, debugging, audit, and recovery within a unified framework. We introduce a taxonomy covering trace sources, evidence and execution units, provenance relations, tracing granularity and timing, representation forms, and trust functions. We then review key methodological directions, including provenance representation, evidence attribution, tool-use provenance, runtime guardrails, provenance-bearing memory, observability, and failure diagnosis. Finally, we discuss benchmarks, datasets, metrics, and open challenges for building provenance-aware, auditable, and recoverable agent systems.

1 Introduction

LLM agents increasingly combine reasoning, retrieval, tools, memory, environmental interaction, and collaboration, making final-answer accuracy insufficient for accountability. The survey unifies evidence tracing and execution provenance to explain support, influence, and failures across agent executions.

  • LLM agents now operate across tools, external knowledge, code, environments, and multi-agent workflows, so intermediate sources, actions, and observations jointly shape outputs.
  • Final-answer accuracy cannot show how outputs were produced, which evidence supported claims, whether tools were justified, how memory influenced decisions, or where failures originated.
  • Execution provenance represents a complete typed agent run, including evidence and execution units connected by causal, procedural, dependency, update, contradiction, and invalidation relations.
  • Evidence tracing projects provenance onto evidence-support and influence relations between evidence units and claims, decisions, or actions, making it a sub-problem of execution provenance.
  • The survey frames retrieval grounding, tool-use safety, memory lineage, observability, debugging, audit, and recovery as connected process-level trust questions.
  • Its contributions include a six-dimensional taxonomy, reviews across seven research threads, provenance-oriented evaluation, and open challenges for unified, semantic, safe, realistic, recoverable, and privacy-aware infrastructure.

2 Taxonomy of Evidence Tracing and Execution Provenance

The survey organizes agent provenance into six dimensions spanning trace sources, recordable units, relations, tracing policy, representations, and trust functions. This taxonomy links classical provenance and observability foundations to LLM-specific semantic dependencies and deployment trade-offs.

  • The taxonomy covers trace sources, evidence and execution units, provenance relations, tracing granularity and timing, representation forms, and trust functions.
  • Trace sources include reasoning, retrieval, tool use, memory, environment interaction, and multi-agent communication, extending provenance beyond model outputs.
  • Evidence units support, contradict, invalidate, or contextualize claims and actions, while execution units record procedural activity such as calls, parameters, memory operations, and actions.
  • Provenance relations combine PROV-compatible USE, GENERATE, and DERIVE with agent-specific SUPPORT, DEPEND-ON, CONTRADICT, INVALIDATE, TRIGGER, and UPDATE relations.
  • Granularity ranges from run-level to token- or span-level tracing, while timing spans pre-execution checks, runtime enforcement, and post-execution analysis.
  • Representation forms include structured logs, execution graphs, evidence and claim-support graphs, provenance graphs, and runtime state representations, with design tensions between accountability and deployability.

3 Provenance Representation and Evidence Attribution

The survey presents provenance representation as layered structures that move from reconstructable logs to dependency graphs and evidence–claim relations. It emphasizes that representation granularity must match the trust function, balancing verification and enforcement against collection and privacy costs.

  • 3.1 From Logs to Execution Graphs: Provenance representation combines structured logs, execution graphs, and evidence–claim graphs to make agent executions reconstructable and dependencies inspectable.Logs record typed events, graphs connect artifacts through typed relations, and evidence graphs distinguish support, contradiction, and omission.
  • 3.1 From Logs to Execution Graphs: Figure 3 models evidence acquisition, claim construction, tool execution, memory updates, and recovery as a typed graph rather than a chronological transcript.Its nodes include queries, passages, claims, tool calls, outputs, memory items, evidence, and actions, connected by relations such as SUPPORT, DERIVE, CONTRADICT, INVALIDATE, and UPDATE.
  • 3.2 Evidence and Claim-Support Attribution: Evidence attribution distinguishes citation from actual support, including supported, unsupported, omitted, contradictory, and invalidating evidence relations.A source may be cited without supporting a claim, while available evidence may be omitted from an answer.
  • 3.3 Representation Trade-offs: Static schemas define provenance object and relation types, while runtime provenance records concrete dependencies among sources, tools, memory, claims, and actions.The two layers support representation and runtime enforcement of execution dependencies.
  • 3.3 Representation Trade-offs: Fine-grained provenance enables claim verification, failure localization, rollback, audit, and policy enforcement but increases storage, privacy, logging, and annotation costs.Claim-level links may suit low-risk retrieval, parameter-level provenance tool use, and memory lineage long-term personalized agents.

4 Execution Provenance in Tool-Using Agents

The survey treats tool use as the outward axis of agent provenance, requiring traces that connect tool selection, argument origins, outputs, influence, and authorization. It synthesizes information-flow tracking, access control, runtime guardrails, and recovery into a shift from logging tool events toward controlling influence.

  • 4.1 Tool-Call Provenance: Tool-use provenance traces why a tool was selected, where its arguments came from, whether its output was reliable, and how it shaped later decisions.Tool calls can retrieve private data, modify state, send messages, execute code, or trigger irreversible actions.
  • 4.1 Tool-Call Provenance: Parameter-level lineage is necessary because legitimate tools can become unsafe when sensitive arguments derive from untrusted or incorrectly generated values.Relevant provenance objects include the selected tool, schema, argument values, execution result, and downstream consumers.
  • 4.2 Indirect Prompt Injection and Tool-Use Contamination: Indirect prompt injection is an information-flow problem in which untrusted external content may influence later tool calls, arguments, memory updates, or external actions.Relations such as DERIVE, DEPEND-ON, TRIGGER, and USE make these influences explicit and distinguish trusted intent from untrusted content.
  • 4.3 Information Flow, Taint Tracking, and Provenance Enforcement: Information-flow defenses track origins and propagation, while instruction separation, taint tracking, execution isolation, and argument monitoring constrain unsafe influence.The cited approaches include Instruction Hierarchy, StruQ, CaMeL, FIDES, NeuroTaint, and Agent-Sentry.
  • 4.4 Access Control and Action Boundaries: Runtime provenance complements access control by making permissions context-sensitive to argument lineage, user intent, trusted outputs, and explicit approval.A read-only search tool may accept untrusted web content, whereas email, database-update, or code-execution tools may require authorized inputs.
  • 4.5 Runtime Guardrails and Verification: Effective guardrails combine semantic provenance for evidence support with procedural provenance for authorized execution paths and trusted inputs.Pre-execution checks, runtime monitoring, and post-execution verification support detection of unsupported claims, contaminated arguments, unauthorized calls, and invalid state updates.
  • 4.6 Summary: The field is shifting from output-only safety and tool logging toward provenance-aware execution control, but unified lineage remains difficult under summarization, paraphrasing, memory consolidation, and multistep reasoning.The proposed next step combines tool lineage, evidence support, source trust, state changes, policy compliance, and recovery dependencies.

5 Memory as Provenance-Bearing Evidence

The survey treats memory items as provenance-bearing evidence whose origins, transformations, validity, conflicts, retrieval, and downstream influence must remain inspectable. This framing connects memory usefulness with accountability across writing, retrieval, reuse, and audit.

  • Memory as provenance-bearing evidence: Memory persists evidence across sessions, where it can support claims, shape plans, fill tool arguments, update other memories, or justify final answers.Accountability therefore requires source lineage, retrieval context, temporal validity, conflict status, and downstream influence.
  • Memory as provenance-bearing evidence: A provenance-aware memory item records its origin, transformations, revisions, validity conditions, and later effects rather than only its stored content.Without these links, long-term memory becomes an opaque evidence source rather than an auditable execution component.
  • Memory writes and lineage: Memory provenance begins at write time by linking each stored item to source type, timestamp, authoring agent, supporting evidence, transformation, confidence, and update history.This allows later verification to inspect the memory’s evidential basis rather than only its surface content.
  • Retrieval and downstream influence: Retrieved memory may be irrelevant, outdated, over-generalized, hallucinated, poisoned, or invalid under current context, making temporal validity and supersession central safeguards.Memory poisoning and injection can steer later responses and actions across sessions.
  • Retrieval and downstream influence: Retrieval is an influence problem: provenance should connect triggering context and retrieved memories to claims, tool calls, actions, final answers, and later memory updates.Such links support judgments about whether memory influence was justified and enable selective invalidation of affected downstream artifacts.
  • Conflicts, contamination, and verification: Persistent memory creates long-horizon provenance failures when incompatible, invalidated, or contaminated information is reused in consequential decisions.Memory quality therefore depends on source trust, write-path legitimacy, conflict status, contamination risk, and later activation, not only recall or coherence.
  • Conflicts, contamination, and verification: Across representative systems, write and retrieval support are common, while conflict handling, staleness detection, contamination tracking, and evidence-aware verification remain limited.A provenance-bearing memory system must combine usefulness from compression and persistence with lineage, validity, conflict tracking, and influence links.

6 Benchmarks, Datasets, and Metrics

Existing benchmarks cover important local capabilities, but full-stack evaluation of evidence tracing and execution provenance remains fragmented. The survey argues for process-level benchmarks that annotate typed relations and test safety, temporal validity, failure localization, and recovery across interacting agent components.

  • Current coverage: Current benchmark families strongly cover local capabilities, but no family provides strong end-to-end coverage across evidence, tools, memory, communication, safety, provenance relations, and recovery.Figure 5 characterizes this as a gap between isolated component evaluation and full-stack provenance assessment.
  • Current coverage: RAG and attribution benchmarks evaluate citation support, faithfulness, hallucination, source supportiveness, and atomic-fact support, but usually connect claims to sources rather than complete execution traces.They are therefore strong evidence-attribution benchmarks but incomplete execution-provenance benchmarks.
  • Current coverage: Agent and tool-use benchmarks extend evaluation to trajectories, tool calls, environment states, policy constraints, external states, adversarial contexts, and indirect prompt injection.These settings shift evaluation from answer correctness toward correct and safe interactive execution.
  • Current coverage: Trace-debugging, memory, and multi-agent benchmarks cover localization, recall, personalization, consistency, multi-session success, and coordination, but remain fragmented across provenance dimensions.Their coverage complements rather than replaces full-stack process evaluation.
  • Core gaps: Few benchmarks evaluate complete cross-component chains from evidence and tool outputs through memory updates, intermediate claims, final answers, external state changes, and recovery actions.Real failures can span several such components, so evaluating one component at a time misses this interaction structure.
  • Core gaps: Typed relation annotation remains underdeveloped: benchmarks should label SUPPORTS, CONTRADICTS, DEPENDS-ON, INVALIDATES, and TRIGGERS relations to measure provenance directly.Without these labels, trace completeness, dependency coverage, memory validity, and cross-agent responsibility are measured only indirectly.
  • Core gaps: Recovery-oriented evaluation is rare, even though provenance should support invalidation, quarantine, retries, human approval, rollback, or compensation after failures and unsafe actions.This extends provenance from post-hoc explanation toward repair and governance.
  • Metrics and benchmark design: Evidence-attribution and safety metrics are relatively established, while trace completeness, provenance accuracy, dependency coverage, and temporal consistency remain mostly proposed.The latter lack agreed definitions or broadly adopted datasets and protocols.

7 Open Problems and Future Directions

Open problems center on fragmented trace schemas, coarse attribution, weak memory and multi-agent lineage, incomplete runtime enforcement, unrealistic benchmarks, and privacy risks. The survey calls for interoperable provenance infrastructure that supports semantic attribution, recovery, and first-class evaluation of trust properties.

  • Unified and Interoperable Trace Schemas: Existing systems rarely provide unified schemas spanning reasoning, retrieval, tools, memory, messages, claims, responses, and external state changes.
  • Claim-Level and Semantic Provenance: Current attribution methods are often too coarse for outputs containing multiple claims, assumptions, and action-relevant inferences.
  • Claim-Level and Semantic Provenance: Semantic provenance must follow evidence across paraphrasing, summarization, memory updates, tool outputs, reflection, and inter-agent communication.
  • Memory and Multi-Agent Provenance: Memory systems provide limited lineage for source, validity, conflicts, updates, retrieval context, and downstream effects on claims or actions.
  • Memory and Multi-Agent Provenance: Multi-agent provenance must attribute failures across communicating, delegating, and jointly deciding agents, steps, and error modes.
  • Runtime Safety and Recovery: Provenance-aware guardrails should track source-to-sink dependencies, while recovery remains an unresolved challenge beyond detection or blocking.
  • Realistic Benchmarks, Privacy, and Governance: Current benchmarks omit realistic combinations of tools, memory, evidence labels, complete traces, and provenance annotations.
  • Overall Direction: The survey calls for interoperable schemas, semantic claim-level attribution, lineage, runtime enforcement with recovery, and benchmarks evaluating traceability, auditability, safety, privacy, and recoverability.

8 Conclusion

As agents retrieve evidence, invoke tools, update memory, interact with environments, and coordinate with other agents, final-answer correctness is insufficient for trustworthiness. The survey reviews provenance approaches and concludes that the field remains fragmented, motivating provenance as infrastructure for traceable, auditable, and recoverable agents.

  • Agent trustworthiness requires exposing answer origins, supporting evidence, tool and action contributions, and points where failures or unsafe influences enter execution.
  • The field has progressed but remains fragmented, with limited fine-grained support, semantic influence tracking, memory lineage, cross-agent propagation, and adversarially robust tracing.
  • The appendix frames the provenance-graph example as a running example for provenance representation rather than appendix-only material.

A.1 Mapping to W3C PROV-DM

The mapping shows that agent provenance can reuse much of the W3C PROV vocabulary while requiring semantic relations that standard bookkeeping does not directly express.

  • Agent execution can align with PROV entities, activities, agents, and core relations, but SUPPORT and CONTRADICT require comparing evidence and claim content.

B Representative Systems Mapped to the Taxonomy

Representative systems occupy different taxonomy dimensions rather than covering the full provenance space. This motivates a unified provenance layer spanning traces, attribution, runtime safety, representations, and trust functions.

  • Trace-source systems produce rich execution units but implement no trust function themselves, serving as substrates for provenance mechanisms.
  • Attribution systems operate post-hoc at claim granularity over retrieval and rarely address tools, memory, or actions.
  • Safety systems operate at runtime on tool parameters but provide little claim-level evidence support.
  • No single reviewed system spans trace sources, fine granularity, runtime timing, explicit representation, and multiple trust functions at once.

C Benchmark Catalogue and Coverage Details

The survey’s benchmark and schema discussion is descriptive: it catalogs what evaluation resources expose and argues that unified agent provenance must combine operational records with semantic evidence relations.

  • Benchmark catalogue: The appendix catalogs evaluation resources by whether they expose evidence labels, tool calls, memory, multi-agent structure, safety perturbations, or trace information.It frames this catalogue as descriptive rather than taxonomic.
  • Provenance foundations: Table 6 maps W3C PROV constructs to agent-provenance counterparts while identifying agent-specific semantic relations and units that PROV does not express.The correspondence uses an upper block for PROV-aligned constructs and a lower block for agent-specific additions.
  • Schema requirements: A unified LLM-agent provenance schema should combine operational execution records with semantic evidence relations.The survey presents this as a central schema requirement.
  • Provenance foundations: Existing standards provide partial foundations through provenance concepts, distributed tracing, data lineage, and structured agent-artifact observability.The cited foundations include W3C PROV-DM, OpenTelemetry, OpenLineage, AgentOps, and AgentTrace.

D.2 Detailed Agenda for Semantic and Claim-Level Provenance

The agenda extends claim-level attribution into semantic provenance that tracks how evidence is transformed and propagated through reasoning, tools, memory, reflection, and communication, while supporting runtime repair.

  • Semantic and claim-level provenance: Claim-level provenance should distinguish citation presence, source relevance, claim support, contradiction, and evidence omission.The survey identifies these as relations often conflated in current systems.
  • Semantic and claim-level provenance: Agentic settings complicate attribution because evidence may be transformed by reasoning, retrieval, tools, memory, reflection, or inter-agent communication before influencing an answer or action.This motivates provenance beyond direct citation links.
  • Semantic and claim-level provenance: Future evaluations should trace how supporting information travels through execution, including multi-source derivations, contradictions, memory summaries, policy constraints, and propagated unsupported assumptions.The survey points to semantic taint and causal influence methods as one possible direction, while calling robust semantic provenance open.
  • Memory and multi-agent provenance: Memory items should expose lineage, validity, trust, and downstream-use metadata when they affect tools, personalization, or long-horizon decisions.The survey connects this requirement to tracing memory poisoning and memory-injection effects.
  • Benchmark implications: Existing benchmarks cover separate provenance components, but few jointly provide evidence labels, tool calls, memory operations, multi-agent communication, safety perturbations, and provenance-relation annotations.This fragmented coverage limits comprehensive evaluation of agent provenance.
  • Runtime enforcement and repair: Runtime provenance should support intervention and repair, not only detection, blocking, or policy enforcement.The proposed response includes identifying contaminated sources, removing derived parameters, requesting confirmation, and preventing contaminated memory writes.

D.5 Benchmark and Governance Requirements

The survey calls for provenance-first benchmarks and governance that evaluate full execution coverage alongside privacy, confidentiality, integrity, safety, and recovery requirements.

  • Benchmark requirements: Future benchmarks should evaluate provenance as a first-class object rather than an implicit by-product of task success.The survey frames benchmark design as part of provenance governance.
  • Schema requirements: Unified provenance schemas must expose structured records and semantic relations needed to represent agent execution and evidence support.Table 9 is presented as a summary of these design requirements.
  • Memory and multi-agent requirements: Memory and multi-agent provenance require dedicated checklists for lineage, trust, downstream use, and message-level traceability.The survey separately identifies Table 10 as covering memory and multi-agent provenance.
  • Coverage requirements: Existing benchmark families separately cover evidence grounding, tool safety, memory, multi-agent coordination, and trace-based failure localization.These families provide partial foundations rather than complete provenance evaluation.
  • Privacy and governance: Provenance quality must be evaluated together with privacy and governance because traces may contain sensitive information, credentials, internal reasoning artifacts, and long-term memories.The survey highlights confidentiality and integrity constraints as relevant governance foundations.
  • Runtime requirements: Runtime safety requirements should include recovery capabilities in addition to enforcement.Table 11 is identified as covering runtime safety and recovery requirements.
  • Benchmark and governance requirements: Realistic provenance benchmarks and governance require dedicated evaluation requirements beyond isolated task success.Table 12 summarizes these benchmark and governance requirements.
Loading 2606.04990v4…