Skip to content

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 agentic evaluation with error propagation tracking [ACL 2026]

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

AgentEval formalizes agentic workflow executions as evaluation 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 (450 test cases), it achieves 2.17× higher failure detection recall (0.89 vs. 0.41) over end-to-end evaluation, \(\kappa = 0.84\) human agreement, and 72% root-cause accuracy against an 81% human ceiling. A 4-month CI/CD-integrated pilot with 18 engineers detected 23 pre-release regressions and reduced median root-cause identification time from 4.2 hours to 22 minutes.

Problem

End-to-end outcome evaluation of multi-step agentic workflows systematically masks intermediate failures: 63% of step-level failures in production traces are propagated from upstream errors, not locally caused, yet E2E evaluation only inspects the final synthesis output. Ad-hoc trace inspection does not scale, and existing ML observability tools (LangSmith, Arize Phoenix, Inspect, etc.) lack formal DAG-based dependency modeling with error propagation tracking and root-cause attribution.

Method

AgentEval represents each agent execution as an evaluation DAG \(G = (V, E, \tau, M)\) where nodes \(V\) correspond to agent steps typed as \(\{PLAN, TOOLSEL, PARAMGEN, EXEC, SYNTH\}\), directed edges \(E\) encode data dependencies, and \(M\) maps each node to type-specific quality metrics. Evaluation proceeds in topological order (Algorithm 1): each node \(v_i\) is scored \(q(v_i) = \text{Eval}(o_i, r_i, c_i, M(\tau(v_i)))\) by a calibrated GPT-4o judge using structured 1–5 rubrics with 5 stratified few-shot calibration anchors per metric. Failed steps (\(q(v_i) < \theta_{\tau(v_i)}\)) are classified via a 3-level, 21-subcategory failure taxonomy derived from 523 disjoint traces. Root-cause attribution uses a greedy heuristic: a failing step with a failing parent is marked as propagated from the lowest-scoring parent; otherwise it is marked a root cause. Non-DAG traces (~12%) are handled via loop unrolling and timestamp-based branch resolution. The framework integrates with CI/CD via GitHub Actions, using paired bootstrap tests (\(p < 0.05\)) and dual-threshold alerting (historical \(2\sigma\) + bootstrap significance) for regression detection.

Key Contributions

  • Evaluation DAG formalization: typed 5-category node schema supporting both schema-defined and trace-inferred DAGs, with structural deviation itself used as a quality signal (deviant traces show 2.1× higher failure rates).
  • Step-level quality metrics: type-specific rubrics evaluated by calibrated LLM-as-judge (GPT-4o, \(\kappa = 0.84\) vs. human experts), with absolute framing for PLAN nodes and upstream-context-relative framing for downstream steps.
  • Hierarchical failure taxonomy: 3 levels / 21 subcategories derived empirically from 523 traces; context loss identified as highest downstream amplifier (3.2× amplification factor).
  • Automated regression suite: CI/CD-integrated with progressive evaluation (fast smoke tests gate full suites, 80% cost reduction during development); 88% precision / 94% recall in regression detection simulation.

Results

  • Failure detection recall: AgentEval 0.89 [0.84, 0.93] vs. E2E 0.41 [0.35, 0.47] (2.17×), Flat Step 0.67 [0.61, 0.73] (+22 pp, \(p < 0.001\)), Rule-Based 0.58.
  • False positive rate: 0.07 [0.04, 0.11], comparable to Rule-Based (0.05) and well below Flat Step (0.15).
  • Human agreement: \(\kappa = 0.84\) [0.79, 0.88] vs. 0.71 (Flat Step), 0.52 (E2E).
  • Root cause accuracy: 72% [0.64, 0.79] vs. human ceiling 81%; 72% of incorrect attributions are within 1 DAG hop of the true root cause.
  • Ablation: removing DAG structure alone costs −22 pp FDRec and −34 pp RCA; this is the single largest contributor.
  • Cross-system generalization (no taxonomy/rubric modification): FDRec ≥ 0.78 on \(\tau\)-bench (retail 0.83, airline 0.79) and SWE-bench (0.78); RCA degrades more sharply (0.52–0.61).
  • DAG advantage scales with workflow length: +15 pp FDRec for ≤3 steps vs. +28 pp for ≥6 steps.
  • Pilot (4 months, 18 engineers): 12,847 traces evaluated; 23 regressions detected (8 genuine, 12 borderline, 3 FP); CS-Agent failure rate 31%→18%; DA-Agent parameter error rate 27%→11%; root-cause time 4.2 hr → 22 min.

Limitations

  • Architecture scope: DAG advantage becomes marginal (<5 pp) above ~60% non-DAG trace rate; unbounded reasoning loops and parallel agent handoffs without explicit dependency declarations defeat DAG reconstruction.
  • Greedy root-cause heuristic: selects the lowest-scoring parent as propagation source—a practical approximation, not formal causal inference; 13% of counterfactual corrections fail to improve downstream scores.
  • RCA degrades on out-of-domain traces: −14 pp on \(\tau\)-bench, −20 pp on SWE-bench, concentrated in novel failure patterns not covered by the existing taxonomy.
  • Judge capability dependency: weaker judges preserve FDRec (GPT-4o-mini: 0.83) but degrade RCA (0.65 vs. 0.72 for GPT-4o); judges substantially weaker than agents become unreliable for attribution.
  • Calibration is few-shot anchoring only: not iterative optimization against a held-out human-labeled set, limiting systematic calibration guarantees.
  • Evaluation cost at scale: ~$2K/day at 100K traces/day with GPT-4o-mini; multi-judge aggregation (3× cost) needed for release-gating.
  • Measurement instrument mismatch: root-cause time reduction (4.2 hr → 22 min) uses self-reported survey for baseline vs. system logs for pilot, limiting quantitative precision.

Relevance to Harnesses / Meta-Harnesses

AgentEval is directly relevant as a meta-evaluation harness for agentic workflows: it instruments multi-step pipelines via an OpenTelemetry-compatible sidecar, reconstructs their execution structure into formal DAGs, and applies a composable evaluation stack (typed metrics → LLM judge → taxonomy → regression detector) that itself acts as a harness layer over arbitrary agent frameworks (LangChain, custom). For researchers building harnesses that orchestrate or evaluate other agents, the DAG formalization of workflow structure and the CI/CD-integrated regression suite represent a reusable pattern for continuous quality monitoring at the meta level—not just task outcomes but the intermediate reasoning and tool-use steps that harnesses must get right. The finding that 63% of failures propagate from upstream steps quantifies why flat, outcome-only evaluation is structurally insufficient for harness correctness, and the ablation isolating DAG dependency modeling as the dominant factor (+22 pp FDRec, +34 pp RCA) provides strong motivation for harness developers to instrument inter-step dependencies explicitly rather than treating pipeline steps as independent.