💻 computer science

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

AgentEval is a framework that formalizes agentic workflows as directed acyclic graphs (DAGs) to enable structured, step-level evaluation and automated root cause attribution, significantly outperforming end-to-end methods in failure detection recall and reducing debugging time in production environments.

Original authors: Dongxin Guo, Jikun Wu, Siu Ming Yiu

Published 2026-04-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Dongxin Guo, Jikun Wu, Siu Ming Yiu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a head chef at a busy restaurant. You have a team of junior cooks (the AI Agents) who work in a sequence: one chops the vegetables, one prepares the sauce, one cooks the meat, and the final cook plates the dish.

Currently, most people evaluate these cooks using "End-to-End Evaluation." This is like a food critic walking in, taking one bite of the final steak, and saying, "This is bad."

The problem? The critic doesn't know why it’s bad. Was the steak overcooked? Was the sauce too salty? Or did the first cook use rotten vegetables? Because the critic only looks at the final plate, the kitchen keeps making the same mistakes, and the head chef has no idea who to retrain.

AgentEval is like installing a high-tech, microscopic camera system in the kitchen that watches every single movement of every single cook.

The Three "Superpowers" of AgentEval

1. The "Recipe Map" (The DAG Structure)

Instead of just looking at the final plate, AgentEval treats the cooking process like a flowchart (a DAG). It knows that the sauce depends on the chopped onions, and the plating depends on the sauce.

The Metaphor: It’s like a detective’s "chain of evidence." If the final dish is ruined, AgentEval doesn't just say "the dish is bad"; it follows the trail of breadcrumbs backward to find exactly where the chain broke.

2. The "Expert Sous-Chef" (The LLM Judge)

To grade the cooks, AgentEval uses a highly trained "Master Chef" (an advanced AI like GPT-4o) to watch every step. This Master Chef doesn't just look at the final result; they grade every individual action:

"Did you chop the onions correctly?" (Step-level metrics)
"Did you pick the right spice?" (Tool selection)
"Did you follow the recipe steps in order?" (Planning)

3. The "Blame Finder" (Error Propagation & Taxonomy)

This is the most important part. In a kitchen, one mistake causes a domino effect. If the first cook uses salt instead of sugar, every cook after them is doomed.

The Metaphor: Most systems see a pile of fallen dominoes and say, "The dominoes fell." AgentEval identifies the "First Domino" (the Root Cause).
It uses a "Failure Taxonomy"—which is basically a very detailed "Wall of Shame." Instead of just saying "you messed up," it says, "You committed a 'Category 2, Subcategory B' error: you used the wrong tool for the job."

Why does this matter in the real world?

The researchers tested this on real AI systems used in customer service and data analysis. Here is what they found:

It’s a Super-Detector: Traditional methods only caught about 41% of mistakes. AgentEval caught 89%. It’s like the difference between a security guard who only checks if the front door is locked versus a guard who monitors every single camera in the building.
It Saves Massive Amounts of Time: In a real-world test, when something went wrong, engineers used to spend over 4 hours hunting for the bug. With AgentEval, they found the problem in just 22 minutes. It turns a long, frustrating scavenger hunt into a quick, targeted fix.
It Prevents "Regressions": Imagine you update your kitchen's oven, and suddenly all the cakes come out flat. AgentEval acts like an automated alarm system that catches these "regressions" before the food ever reaches a customer.

Summary

AgentEval moves AI evaluation from "Did it work?" to "Exactly where, how, and why did it fail?" It turns the "black box" of AI workflows into a transparent, step-by-step map, allowing developers to fix the "first domino" rather than just complaining about the fallen pile.

Technical Summary: AgentEval: DAG-Structured Step-Level Evaluation

AgentEval is a novel evaluation framework designed to address the critical "evaluation gap" in production-grade agentic AI systems. As agents move from simple chatbots to complex, multi-step workflows, traditional end-to-end (E2E) evaluation methods fail to identify where exactly a reasoning chain or tool-use sequence breaks down.

1. The Problem: The "Masking" Effect of End-to-End Evaluation

Current evaluation practices for AI agents suffer from three primary flaws:

Error Masking: E2E metrics (checking only the final output) fail to detect intermediate failures. An agent might make a correct plan but fail a tool call, or vice versa; E2E evaluation only sees the final incorrect result, masking the true source of the error.
Error Propagation: In agentic workflows, errors are not isolated; they compound. A small mistake in a "Planning" step cascades through "Tool Selection" and "Parameter Generation," making root-cause attribution difficult.
Lack of Scalability: Manual trace inspection is too slow for modern CI/CD pipelines, while static benchmarks do not reflect the dynamic, continuous deployment needs of real-world organizations.

2. Methodology: The AGENTEVAL Framework

The authors propose formalizing agent executions as Evaluation Directed Acyclic Graphs (DAGs). The framework consists of four integrated components:

Evaluation DAG Formalization: Every agent step is treated as a node in a DAG. Each node is typed (e.g., PLAN, TOOLSEL, EXEC, SYNTH) and carries specific quality metrics. This structure allows the system to track how a failure in one node affects its descendants.
Step-Level Quality Metrics (LLM-as-Judge): Instead of a single score, AGENTEVAL uses a calibrated LLM (GPT-4o) to score each step based on type-specific rubrics. To prevent circular bias, the judge is from a different model family than the agent being evaluated.
Hierarchical Failure Taxonomy: The authors developed a 3-level taxonomy (21 subcategories) to classify failures (e.g., "Context Loss" $\rightarrow$ "Truncation"). This provides semantic depth to error reporting.
Automated Root Cause Attribution (RCA): Using a greedy heuristic, the framework traverses the DAG. If a step fails, the system checks its parents; if a parent also failed, the error is marked as "propagated." If no parents failed, the step is identified as the "root cause."

3. Key Contributions

Structural Dependency Modeling: Moving from "flat" step evaluation to DAG-based evaluation, enabling the tracking of error propagation.
A Calibrated Metric Suite: A robust set of rubrics and few-shot anchors that achieve high human alignment ( $\kappa = 0.84$ ).
A Diagnostic Taxonomy: A data-driven classification system derived from hundreds of real-world agent traces.
CI/CD Integration: A practical regression suite that allows engineers to block deployments if new model/prompt updates cause step-level regressions.

4. Key Results

The framework was tested across three production workflows (Customer Service, Data Analysis, and Document Processing) and compared against E2E and "Flat" step-level baselines:

Superior Failure Detection: AGENTEVAL achieved a Failure Detection Recall (FDRec) of 0.89, which is 2.17× higher than E2E evaluation (0.41).
Ablation Insights: The DAG structure was found to be the most critical component, contributing +22 percentage points to failure detection recall and +34 pp to root cause accuracy compared to flat evaluation.
High Accuracy & Alignment: The system achieved 72% Root Cause Accuracy (approaching the 81% human ceiling) and showed strong agreement with human experts ( $\kappa = 0.84$ ).
Real-World Impact: In a 4-month pilot, the framework reduced the median time for root-cause identification from 4.2 hours to 22 minutes and helped detect 23 pre-release regressions.

5. Significance

AgentEval shifts the paradigm of agent evaluation from outcome-oriented (did it work?) to process-oriented (why did it fail?). By providing a mathematically structured way to attribute errors, it enables engineers to move from "guessing" why an agent failed to "knowing" exactly which step requires a prompt update or a tool fix. This is essential for the reliability and scaling of autonomous AI agents in enterprise environments.