PaperlayerView exact revision on arXiv

Source-linked AI summary

AgentEval: DAG-Structured Step-Level Evaluation for Agentic Workflows with Error Propagation Tracking

Dongxin Guo, Jikun Wu, Siu Ming Yiu

arXiv:2604.23581v1cs.SEcs.CL

TL;DR

Existing agent evaluation often relies on end-to-end outcomes or manual inspection, despite workflows having heterogeneous steps and dependencies through which errors propagate. AgentEval evaluates workflows as DAGs with typed step metrics, a failure taxonomy, and root-cause attribution. On predominantly sequential production workflows, it reports higher failure detection recall than end-to-end evaluation, with transferability also observed on two external benchmarks.

  • Problem

    Agent evaluation lacks deployment-oriented infrastructure that combines intermediate-step assessment with dependency-aware analysis and continuous monitoring.

    Source: §1 · p. 1

  • Method

    AgentEval represents workflows as evaluation DAGs with typed metrics, uses LLM-judged step scoring and a hierarchical failure taxonomy, and tracks upstream dependencies for attribution.

    Source: §1 · p. 1, §3.1 · p. 2, §3.2 · p. 3

  • Results

    2.17× higher failure detection recall than end-to-end evaluation; AgentEval also reports κ = 0.84 human agreement, 72% root cause accuracy versus an 81% human ceiling, and FDRec ≥0.78 on τ-bench and SWE-bench.

    Source: §5.1 · p. 5, §7 · p. 7

  • Takeaways & Limitations

    DAG-based dependency modeling is the single most impactful component in the ablation, with an advantage that grows with workflow complexity and holds across four judge models.

    Source: §5.2 · p. 5, §7 · p. 7

    The evaluation centers on predominantly sequential architectures; the DAG advantage diminishes beyond ∼60% non-DAG trace rates, and core results come from one organization.

    Source: Limitations · p. 8

Abstract

from arXiv · show

Agentic systems that chain reasoning, tool use, and synthesis into multi-step workflows are entering production, yet prevailing evaluation practices like end-to-end outcome checks and ad-hoc trace inspection systematically mask the intermediate failures that dominate real-world error budgets. We present AgentEval, a framework that formalizes agent executions as evaluation directed acyclic graphs (DAGs), where each node carries typed quality metrics assessed by a calibrated LLM judge (GPT-4o), classified through a hierarchical failure taxonomy (3 levels, 21 subcategories), and linked to upstream dependencies for automated root cause attribution. An ablation study isolates the impact of DAG-based dependency modeling: it alone contributes +22 percentage points to failure detection recall and +34 pp to root cause accuracy over flat step-level evaluation with identical judges and rubrics. Across three production workflows (450 test cases, two agent model families, predominantly sequential architectures with a 12% non-DAG trace rate), AgentEval achieves 2.17x higher failure detection recall than end-to-end evaluation (0.89 vs. 0.41), Cohen's kappa = 0.84 agreement with human experts, and 72% root cause accuracy against an 81% human ceiling. Cross-system evaluation on tau-bench and SWE-bench traces confirms transferability (failure detection recall >= 0.78) without taxonomy or rubric modification. A 4-month pilot with 18 engineers detected 23 pre-release regressions through CI/CD-integrated regression testing, reducing median root-cause identification time from 4.2 hours to 22 minutes and driving measurable failure rate reductions in two workflows.

1 Introduction

Agentic workflows need evaluation that can assess intermediate steps and their dependencies, not only final outcomes. AgentEval is presented as infrastructure for addressing this gap.

1 Introduction

  • Current end-to-end metrics can mask intermediate failures, while manual inspection does not scale and static benchmarks are disconnected from deployment constraints.The cited constraints include latency, cost, and continuous integration.Source: §1 · p. 1
  • Agent workflows have heterogeneous step types and DAG dependencies through which errors can propagate and compound.The paper adapts process-supervision insights to inference-time assessment using expert-annotated ground truth and continuous deployment infrastructure.Source: §1 · p. 1
  • AgentEval is introduced as evaluation infrastructure addressing these challenges through four contributions.Source: §1 · p. 1

1. Evaluation DAG formalization: representing

AgentEval combines DAG-based step evaluation, a failure taxonomy, and regression testing; the paper reports improved failure detection and root-cause attribution on production workflows.

  • AgentEval formalizes agent workflows as DAGs with typed step metrics, a hierarchical failure taxonomy, and automated regression testing.On three predominantly sequential production workflows, it reports 2.17× higher failure detection recall than end-to-end evaluation, κ = 0.84 human agreement, and 72% root cause accuracy.Source: §1 · p. 2

2 Related Work

Prior work covers agent benchmarks, process supervision, and LLM-as-judge evaluation, while the paper distinguishes deployment infrastructure as a remaining need.

Agent Evaluation and Process Supervision

  • Existing agent benchmarks assess capabilities in controlled settings, whereas deployment calls for continuous monitoring, regression detection, and CI/CD integration.LATS provides per-step value estimates for planning.Source: §2 · p. 2
  • Process-supervision studies find that intermediate-step evaluation outperforms outcome-only evaluation, and other work identifies error propagation as a primary agent-performance bottleneck.The cited work includes Lightman et al. (2024), Uesato et al. (2022), Cemri et al. (2025), and Zhu et al. (2025).Source: §2 · p. 2
  • The LLM-as-judge paradigm enables scalable evaluation with >80% human agreement.Source: §2 · p. 2

Production Infrastructure

  • The paper says surveyed production-monitoring tools do not provide formal DAG dependency modeling with error-propagation tracking and root-cause attribution.It characterizes its attribution approach as a practical greedy heuristic rather than formal causal inference.Source: §2 · p. 2

3 The AGENTEVAL Framework

AgentEval integrates DAG-based workflow representation, step metrics, a failure taxonomy, and a regression suite. Its components support structured assessment and deployment monitoring.

3 The AGENTEVAL Framework

  • AgentEval integrates a formal workflow DAG, LLM-judged step metrics, a hierarchical failure taxonomy, and an automated regression suite.Source: §3 · p. 2

3.1 Agent Workflow as Evaluation DAG

  • An evaluation DAG represents agent steps as typed nodes with directed dependency edges and metrics selected for each step type.Nodes can carry parent context, outputs, and optional references; the framework supports adding step types and metric sets.Source: §3.1 · p. 2
  • DAGs enable independent step assessment and error-propagation tracking; the framework supports schema-defined and trace-inferred structures.It handles ∼12% non-DAG traces using loop unrolling and timestamp-based branch resolution, with 0.8% falling back to flat evaluation.Source: §3.1 · p. 2, Figure 1 · p. 3
  • Deviant traces were associated with 2.1× higher failure rates than conformant traces, an observational pattern that does not establish malfunction or causation.Source: §3.1 · p. 3

3.2 Step-Level Quality Metrics

  • Step-specific metrics are scored by GPT-4o using a 1–5 rubric and few-shot anchors; PLAN uses the original query, while later steps use their local upstream context.Downstream prompts include prior outputs but not prior judge scores, avoiding bias toward agreement with upstream attributions.Source: §3.2 · p. 3

3.3 Hierarchical Failure Taxonomy

  • The failure taxonomy has three levels, including 9 Level 2 categories for detection and 21 Level 3 subcategories for diagnostic detail.It was derived from 523 traces disjoint from the evaluation cases; context loss has the highest downstream amplification factor, 3.2×.Source: §3.3 · p. 3, Table 1 · p. 4

3.4 Automated Regression Suite

  • The regression suite versions evaluations, detects regressions with paired-bootstrap tests and dual-threshold alerts, and can block critical deployments through GitHub Actions.The core procedure processes DAG nodes in topological order and uses the lowest-scoring parent as the propagation source when multiple parents score poorly.Source: §3.4 · pp. 3–4

4 Experimental Setup

The evaluation uses three production-representative workflows and a human-annotated, step-level test set. AgentEval is compared with end-to-end, flat step-level, and rule-based baselines using multiple quality metrics.

4.1 Agent Workflows

  • The three workflows are customer service, data analysis, and document processing pipelines using the same tools and prompt templates as their production counterparts on anonymized historical queries.Source: §4.1 · p. 4

4.2 Evaluation Dataset

  • The evaluation set contains 450 test cases—150 per workflow—with stratified sampling of typical and edge cases and expert step-level annotations.Five domain experts annotated 987 steps across 150 traces; 195 steps rated 2 or lower form the failure-recall denominator.Source: §4.2 · p. 4

4.3 Baselines and Metrics

  • The baselines are end-to-end-only and flat step evaluation with GPT-4o, plus 47 hand-crafted workflow rules; reported metrics include FDRec, FPR, human agreement, and RCA.AgentEval-versus-Flat Step results are reported on 150 human-annotated test cases with 95% bootstrap confidence intervals; the listed differences are significant at p < 0.001 for FDRec, HA, and RCA.Source: §4.3 · pp. 4–5, Table 3 · p. 5

5 Results and Analysis

AgentEval improves failure detection and root-cause attribution over comparison methods, with DAG dependency modeling producing the largest ablation effect. Its results also examine regression detection, cross-system transfer, and architecture scope.

5.1 Main Results

  • FDRec is 0.89 for AgentEval versus 0.41 for E2E and 0.67 for Flat Step; human agreement is κ = 0.84 and root cause accuracy is 72% against an ∼81% human ceiling.Source: §5.1 · p. 5

5.2 Ablation Study

  • Removing DAG structure causes the largest degradation (−22 pp FDRec, −34 pp RCA), while replacing the LLM judge causes a −27 pp FDRec drop.Removing the taxonomy primarily affects RCA (−18 pp), and removing calibration anchors primarily affects human agreement (−8 pp κ).Source: Table 4 · p. 5, §5.2 · p. 5

5.5 Architecture Scope Analysis

  • Under increased non-DAG rates, the DAG advantage remains significant up to ∼60%, then becomes marginal (<5 pp); performance degrades moderately (FDRec 0.82, RCA 0.58) yet stays above flat evaluation.Structures that can defeat reconstruction include long unbounded reasoning loops and parallel agent handoffs without explicit dependency declaration.Source: §5.1 · p. 5, §5.5 · p. 6

5.2 Ablation Study

  • Context loss has a 3.2× average downstream amplification factor, while execution failures account for 42–55% across workflows.The reported results are robust across four judge models, with the DAG advantage significant for each.Source: §5.2 · p. 5

5.3 Regression Detection

  • Regression detection achieves 88% precision and 94% recall across six simulated update scenarios; E2E evaluation requires 4× more test cases for equivalent statistical power.The pilot organically detected 23 regressions: 8 genuine, 12 borderline, and 3 false positives.Source: §5.3 · p. 6

5.4 Cross-System Generalization

  • Without taxonomy or rubric changes, cross-system evaluation reports FDRec ≥0.78, while root-cause accuracy declines on novel failure patterns outside the taxonomy.The authors report valid DAG parses for 90% of τ-bench traces and 89% of SWE-bench traces.Source: §5.4 · p. 6

6 Deployment Experience

The four-month pilot replaced manual root-cause investigation with automated propagation-aware analysis, while targeted fixes reduced failures in two workflows. Deployment used asynchronous evaluation, and the pilot time comparison uses different measurement instruments.

6 Deployment Experience

  • Evaluation ran asynchronously with a tiered judge fallback, with step-level evaluation taking about 2 seconds per step and GPT-4o-mini costing about $0.02 per trace.At 100K traces per day, the estimated daily cost was about $2K; multi-judge aggregation was recommended for release gating only.Source: §6 · pp. 6–7
  • 4.2 hours to 22 minutes: median root-cause identification time fell during the pilot, though baseline and pilot measurements used different instruments.The directional improvement was consistent across all three teams.Source: §6 · p. 7, Table 6 · p. 7
  • An upstream context-truncation bug caused 23% of CS-Agent failures; fixing it reduced that workflow’s failure rate by 8 percentage points.For DA-Agent, parameter hallucination accounted for 31% of execution failures, and targeted few-shot examples reduced the parameter error rate from 27% to 11%.Source: §6 · p. 7

7 Conclusion

AgentEval formalizes workflows as evaluation DAGs with step-level quality metrics, a hierarchical failure taxonomy, and automated regression testing. On three predominantly sequential production workflows, it improved failure detection recall over end-to-end evaluation, with human agreement and root-cause accuracy also reported.

7 Conclusion

  • AgentEval combines evaluation DAGs, step-level quality metrics, a hierarchical failure taxonomy, and automated regression testing.The conclusion describes the evaluated production workflows as predominantly sequential.Source: §7 · p. 7
  • 2.17× higher failure detection recall than end-to-end evaluation; human agreement was κ = 0.84 and root cause accuracy was 72%, approaching the 81% human ceiling.The ablation identifies DAG-based dependency modeling as the most impactful component; cross-system evaluation reports transferability to τ-bench and SWE-bench (FDRec ≥0.78).Source: §7 · p. 7
  • Future work includes cycle-aware graphs for multi-agent systems, automated taxonomy evolution, and integrating evaluation signals into agent training loops.Source: §7 · p. 7

Limitations

The reported evaluation centers on predominantly sequential architectures and one organization, with cross-system evidence from two external benchmarks; the authors identify limits for highly dynamic multi-agent systems.

Limitations

  • The DAG advantage diminishes beyond about 60% non-DAG traces, limiting applicability to highly dynamic multi-agent systems.The authors also note single-organization core results, residual judge-model bias, heuristic rather than formal-causal RCA, and caution about the pilot comparison’s different measurement instruments.Source: Limitations · p. 8

Ethical Considerations

These sections describe ethical safeguards, trace handling, taxonomy and judge procedures, and analyses of agreement, attribution errors, strategy tradeoffs, and evaluation scope. Together they specify how results were produced and where performance or applicability is bounded.

Ethical Considerations

  • The evaluation used anonymized historical queries without personally identifiable information, and the taxonomy was developed from internal data that may not cover all deployment contexts.The authors also acknowledge residual judge-model bias despite cross-family evaluation design.Source: Ethical Considerations · p. 8

A Non-DAG Trace Handling

  • About 12% of traces were non-DAG, handled by unrolling retry loops and resolving dynamic branches from timestamps; 0.8% fell back to flat evaluation and manual review.Source: A Non-DAG Trace Handling · p. 9

B Full Failure Taxonomy

  • The taxonomy was built from 523 development traces, with categories locked before evaluation annotations; evaluation data confirmed coverage but did not refine the taxonomy.Pilot feedback later proposed three additional subcategories through a propose-discuss-merge process.Source: B Full Failure Taxonomy · pp. 9–10

C LLM-as-Judge Prompt Templates

  • The TOOLSEL and PLAN judge prompts use separate 1–5 rubrics: tool selection is rated for fit to the subtask, while planning is rated for completeness, feasibility, and ordering.Source: §C.1 · p. 10, §C.2 · p. 10

D Human Agreement by Score Subset

  • Human agreement remained substantial on failures, with κ ≥0.69, supporting that overall κ = 0.84 was not inflated by majority-class agreement.Source: Table 9 · p. 10

E RCA Error Analysis

  • Among incorrect root-cause attributions, multi-branch convergence accounted for 41%, long propagation chains 33%, and threshold boundary cases 26%; median error distance was one hop.72% of errors were within one hop and 91% within two hops; random assignment had a mean distance of 2.8 hops.Source: E RCA Error Analysis · p. 10

F RCA Attribution Strategy Comparison

  • Full-path minimum improved RCA by 3 percentage points but increased false attribution from .06 to .14, so greedy lowest-parent was selected as the default.Weighted propagation offered a 1-point RCA improvement with 3-point higher false attribution; it may suit deployments with reliable edge-confidence signals.Source: F RCA Attribution Strategy Comparison · pp. 10–11, Table 10 · p. 10

K Architecture Scope Details

M Deployment Methodology Details

Deployment analyses report shorter root-cause identification times, characterize propagated failures and operational lessons, and identify boundaries in measurement and generalization.

M Deployment Methodology Details

  • 22 minutes with AgentEval versus 4.2 hours at baseline was the median root-cause identification time, but the measurements used different instruments and include confounds.AgentEval times capture alert-to-first-code-change and may exclude initial investigation; the baseline is self-reported and may include communication overhead.Source: M Deployment Methodology Details · p. 12

N Deployment Lessons Learned

  • 34% of CS-Agent failures involved parameter hallucination errors missed by initial metrics, while uncalibrated judges showed 15% lower agreement.The authors recommend starting with failure modes; five stratified anchors per metric were the minimum, and random anchors underperformed with skewed score distributions.Source: N Deployment Lessons Learned · pp. 12–13
  • Deviant traces were associated with 2.1× higher failure rates, smoke-test adopters ran 3.4× more evaluation cycles per sprint, and three taxonomy subcategories were added during the pilot.The authors describe schema-defined and trace-inferred DAGs as complementary and used a propose-discuss-merge protocol for taxonomy governance.Source: N Deployment Lessons Learned · p. 13

O Extended Limitations

  • The dataset does not reflect full live-system complexity, and the taxonomy was derived from three workflow types; cross-system evaluation found 76% out-of-domain taxonomy coverage.The evaluation used 150 human-annotated cases, and workflows were English-language only.Source: O Extended Limitations · p. 13

P Threshold Sensitivity Analysis

  • A ±0.5 threshold shift changed failure-detection recall by ±4 percentage points for PARAMGEN, versus ±2 points for other step types.The workflow-level score uses a weighted harmonic mean; the equation’s desc(v_i) denotes the descendants of v_i.Source: P Threshold Sensitivity Analysis · p. 13

Q Counterfactual Analysis

  • Across 30 sampled failing traces, counterfactual analysis confirmed AgentEval-identified root causes in 87% of cases.Replacing the CS-Agent root cause at v2 with the gold-reference output improved downstream scores at v3, v4, and v5.Source: Q Counterfactual Analysis · p. 13

R Systematic Disagreement Patterns; S Parsing Failure Analysis; W Score Distribution and Confusion Matrix

T Error Propagation Statistics

  • 63.2% of 847 step-level failures were propagated, with average propagation chains of 2.1 steps.Context loss failures had the longest average chain (3.2 steps), while API/tool failures had the shortest (1.4 steps).Source: T Error Propagation Statistics · p. 14
Loading 2604.23581v1…