Skip to content

AgentTrails: Towards Trust and Reuse for Agentic Tasks

🕒 Published (v1): 2026-07-21 07:53 UTC · Source: Arxiv · link

Why this paper was selected

Freire group (NYU); provenance and trust framework for reusable agent task trajectories

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

AgentTrails is a prototype system that converts raw LLM agent execution logs into structured provenance graphs, making dataflow dependencies explicit rather than buried in chronological traces. It further supports multi-trace comparison via a "joined quotient graph" that aligns recurring tool-use patterns across stochastic executions. The system enables debugging, workflow validation, and reusable skill identification from heterogeneous agent trajectories.

Problem

Raw agent trajectories are stored as chronological text logs that obscure the underlying dataflow: dependency edges between tool calls and intermediate artifacts are implicit, making it hard to (1) understand what a single execution actually did structurally, (2) compare divergent runs of the same task, and (3) identify reusable sub-workflows or diagnose failures. Existing tools focus on single-run inspection or require instrumentation of the running framework; none reconstruct provenance post-hoc and align multiple executions.

Method

AgentTrails operates in three coordinated stages:

  1. Trace Overview: Normalizes each trace \(T_r = \langle c_{r,1}, \ldots, c_{r,n_r} \rangle\) into a tool-coverage matrix \(M_{r,u} = |\{i : \text{tool}(c_{r,i}) = u\}|\), displayed as an UpSet-style view with optional Shapley-style tool-impact scores alongside trace-level metrics (score, cost, latency, tokens).

  2. Provenance Graph Construction: Converts a single trace into a bipartite graph \(G_T = (A_T \cup E_T, R_T)\) where \(A_T\) are tool-call activities and \(E_T\) are data entities (inputs, outputs, artifacts). Dependency edges are recovered via evidence-based reconstruction: exact edges are added when a later call's arguments reference keys from earlier outputs (\(e_j \to a_i\) iff \(K(e_j) \cap \text{refs}(c_i.\text{args}) \neq \emptyset\), \(j < i\)); weaker semantic candidates (shared tokens, query terms, column names) are flagged and refined by a constrained LLM that emits only graph patch operations preserving temporal order and bipartite schema.

  3. Joined Quotient Graph: Each activity is abstracted into a capsule encoding tool identity, I/O structure, local graph context, and upstream root lineage. Capsules are clustered across traces using a weighted similarity \(S(\kappa_i, \kappa_j) = \sum_m w_m s_m(\kappa_i, \kappa_j)\) (Jaccard/cosine over feature components, \(\sum w_m = 1\)). Clusters become joined activity nodes; original provenance edges are remapped by cluster assignment. Joined nodes store support counts, per-trace multiplicity, and score summaries, making high-support motifs and low-support anomalies visually distinguishable.

An LLM-based provenance copilot sits atop these graph views for interactive sensemaking but does not alter the graph structure.

Key Contributions

  • Provenance framing for tool-calling agents: models tool calls as computational activities and their I/O as data entities in a PROV-style bipartite graph, reconstructed post-hoc without framework instrumentation.
  • Evidence-based dependency reconstruction: a staged pipeline combining exact key-match edges, semantic candidate generation, and constrained LLM refinement with auditability (each edge type remains distinguishable).
  • Joined quotient graph: a multi-trace alignment abstraction using activity capsules and weighted similarity clustering; the first approach to align stochastic agent executions at the provenance level rather than as flat sequences.
  • Visual analytics system: coordinated UpSet overview, single-trace provenance inspector, and joined comparison view with support/score-driven filtering.
  • Preliminary gold benchmark: 10 hand-annotated traces with 234 gold dependency edges as a first step toward provenance quality evaluation.

Results

  • Demonstrated on SciAgentGym (physics task 27, hyperfine transition frequency): provenance graph revealed fan-in/fan-out computation structure (independent physical constants converging into hyperfine constant \(A\), then branching into energy-shift calculations) that was not apparent from the raw sequential log.
  • Demonstrated on Discovera (gene-set Signature-to-Mechanisms task s2m_task_016): joined graph showed that the top-scoring trace follows a direct, compact dataflow (csv_record → filter FDR < 0.05 → csv_select → csv_join → ora_pipe), while lower-scoring traces introduce off-path branches visible as low-support detours in the joined view.
  • Preliminary provenance reconstruction evaluated on 10 manually annotated traces (234 gold edges); described as "promising" but no precision/recall numbers are reported.

Limitations

  • No quantitative provenance-quality evaluation beyond a preliminary hand-annotated set of 10 traces / 234 edges; full staged evaluation is ongoing.
  • Capsule similarity weights \(w_m\) are not principled—no ablation or tuning methodology is provided.
  • Scalability to very long traces or large trace collections has not been assessed.
  • The joined graph abstraction design space is largely unexplored; alternative alignment strategies (role-aware, retrieval-based blocking) are left to future work.
  • The system is a prototype (VLDB workshop paper); no user study or controlled comparison against baseline tools is reported.

Relevance to Agentic AI / LLM Agents

AgentTrails directly addresses a gap in the agentic AI infrastructure: while considerable work has gone into making agents more capable, understanding and auditing what they actually did—and why—remains difficult. By reframing agent trajectories as provenance graphs, the system enables principled debugging (tracing failures to specific upstream artifacts), workflow validation (verifying scientific tool-use chains against expected dependencies), and skill extraction (identifying high-support reusable motifs), all of which are prerequisites for trustworthy deployment of agentic systems. The joined quotient graph is particularly relevant to researchers studying agent stochasticity and evaluation, as it provides a structural way to compare divergent executions beyond sequence-level metrics. This work complements trajectory-replay and skill-distillation approaches (ExpeL, Trace2Skill, Reflexion) by exposing internal dependency structure rather than treating traces as opaque sequences.