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

🕒 Published (v1): 2026-04-26 07:38 UTC · Source: Arxiv · Venue: ACL 2026 · link

Why this paper was selected

DAG-structured step-level evaluation with error propagation tracking for agent workflows

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

AgentEval formalizes agentic workflow evaluation as directed acyclic graphs (DAGs) where each node carries typed quality metrics assessed by a calibrated LLM judge, enabling step-level failure detection with automated root-cause attribution via error propagation tracking. On three production workflows, it achieves 2.17× higher failure detection recall than end-to-end evaluation (0.89 vs. 0.41) with κ = 0.84 human agreement. A 4-month CI/CD-integrated pilot reduced median root-cause identification time from 4.2 hours to 22 minutes.

Problem

End-to-end outcome checks mask intermediate failures in multi-step agentic workflows, and ad-hoc trace inspection does not scale to production. Prior step-level approaches evaluate steps independently, missing that 63% of step-level failures propagate from upstream errors rather than arising locally — making dependency-aware evaluation essential but absent from existing tooling (LangSmith, Arize Phoenix, Inspect, etc.).

Method

Agent execution traces are parsed into evaluation DAGs \(G = (V, E, \tau, M)\) where nodes correspond to agent steps typed as \(T = \{\text{PLAN}, \text{TOOLSEL}, \text{PARAMGEN}, \text{EXEC}, \text{SYNTH}\}\), edges encode data dependencies, and each node's metric set \(M(v_i)\) is determined by its type. Nodes are processed in topological order; a calibrated GPT-4o judge (temperature 0, 5 few-shot anchors per metric, absolute framing for PLAN and context-relative framing for downstream steps) assigns a 1–5 quality score \(q(v_i) = \text{Eval}(o_i, r_i, c_i, M(\tau(v_i)))\).

Failures are classified via a three-level taxonomy (3 levels, 21 subcategories) derived from 523 traces disjoint from evaluation data. Root cause attribution uses a greedy heuristic: a failing node with at least one failing parent is marked propagated from the lowest-scoring parent; otherwise it is marked root cause. An automated regression suite integrates with CI/CD via paired bootstrap tests (\(p < 0.05\)) with dual-threshold alerting, and progressive evaluation (fast 10-case smoke tests gate full 100+ case suites).

Key Contributions

• Evaluation DAG formalization: typed step nodes with dependency edges enable propagation-aware step evaluation and counterfactual root-cause validation.
• Calibrated LLM-as-judge: GPT-4o with per-type rubrics and 5 few-shot anchors achieves κ = 0.84 human agreement (κ = 0.76 on failing-step subset).
• Hierarchical failure taxonomy: 3 levels, 21 subcategories derived from 523 traces; context loss carries the highest downstream amplification factor (3.2×).
• CI/CD regression suite: paired bootstrap detection with 88% precision / 94% recall; 80% cost reduction via progressive evaluation.
• Ablation isolating DAG contribution: DAG structure alone adds +22 pp FDRec and +34 pp RCA over flat step evaluation with identical judges.

Results

• Failure Detection Recall (FDRec): AgentEval 0.89 [0.84, 0.93] vs. E2E 0.41, Flat Step 0.67, Rule-Based 0.58.
• False Positive Rate: 0.07, comparable to E2E (0.08) and lower than Flat Step (0.15).
• Human Agreement: κ = 0.84 vs. κ = 0.52 (E2E), κ = 0.71 (Flat Step).
• Root Cause Accuracy: 72% [0.64, 0.79] vs. human ceiling 81%; Flat Step 38%, Rule-Based 45%.
• Cross-system generalization (no taxonomy changes): τ-bench FDRec 0.79–0.83, RCA 0.55–0.61; SWE-bench FDRec 0.78, RCA 0.52 — all above E2E baselines (FDRec 0.35–0.38).
• Ablation: removing DAG structure → −22 pp FDRec, −34 pp RCA; removing LLM judge → −27 pp FDRec; removing taxonomy → −18 pp RCA; removing calibration → −8 pp κ.
• DAG advantage scales with workflow length: +15 pp FDRec for ≤3 steps vs. +28 pp for ≥6 steps.
• Pilot (4 months, 18 engineers): 23 pre-release regressions detected, CS-Agent failure rate 31%→18%, DA-Agent parameter error rate 27%→11%, median root-cause time 4.2 hr → 22 min.

Limitations

• Architecture scope: DAG advantage becomes marginal (<5 pp) above ~60% non-DAG traces; unbounded reasoning loops and parallel agent handoffs without explicit dependency declarations resist reconstruction.
• Root cause attribution uses a greedy heuristic (lowest-scoring parent), not formal causal inference; 72% of incorrect attributions are within 1 DAG hop.
• Taxonomy and RCA degrade on out-of-domain benchmarks (−14 pp RCA on τ-bench, −20 pp on SWE-bench) due to novel failure patterns; domain extension requires ~12–30 person-hours onboarding.
• Evaluation primarily covers predominantly sequential architectures (12% non-DAG rate); extension to multi-agent and cyclic settings is left as future work.
• Root-cause time comparison uses different measurement instruments (survey vs. system logs), limiting precise magnitude claims.
• Judge calibration uses stratified few-shot anchoring, not iterative optimization against a held-out human-labeled set.

Relevance to Agentic AI / LLM Agents

AgentEval directly addresses the evaluation infrastructure gap that limits reliable deployment of LLM agents: while most agentic benchmarks measure final task success, this work demonstrates that 63% of step-level failures propagate from upstream errors, making dependency-aware intermediate evaluation essential for diagnosing real agent behavior. The DAG formalization and hierarchical failure taxonomy (particularly the 3.2× amplification factor of context loss) provide actionable diagnostic primitives for agent developers. The CI/CD integration and LLM-as-judge approach make this practical for continuous monitoring of production deployments rather than one-shot benchmark evaluation. This complements process supervision and reward modeling research by operating at inference time without ground-truth rewards, and the cross-system transferability results (FDRec ≥ 0.78 on τ-bench/SWE-bench) suggest the DAG evaluation paradigm is broadly applicable across agent architectures.