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

• URL: http://arxiv.org/abs/2604.23581v1
• Date: Sun, 26 Apr 2026 07:38:47 GMT
• Title: AgentEval: DAG-Structured Step-Level Evaluation for Agentic Workflows with Error Propagation Tracking
• Abstract summary: We present AgentEval, a framework that formalizes agent executions as evaluation directed acyclic graphs (DAGs)<n>AgentEval achieves 2.17x higher failure detection recall than end-to-end evaluation and 72% root cause accuracy against an 81% human ceiling.
• Score: 13.891522069967507
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• CockpitHAT: Dependency-Graph-Driven Hierarchical Attribution for Embodied Multi-Agent Cockpits [3.9502278152528625]
  LLM multi-agent systems suffer from Correctness Collapse, where high task-level accuracy conceals severe process-level failures.<n>We introduce CockpitHAT, a hierarchical attribution framework that replaces positional windows with dependency-distance thresholds from interaction DAGs.<n>We release CockpitBench, a benchmark of 212 annotated failure traces spanning dialogue, vehicle-state, environmental severity, and memory channels.
  arXiv  Detail & Related papers  (2026-08-03T07:13:00Z)
• Measurement Without Validity: The Compounding Reliability Problem in Agentic AI Evaluation [0.0]
  Agentic AI evaluation pipelines produce benchmark scores that justify deployment decisions, safety certifications, and regulatory compliance claims.<n>No formal framework has yet characterized how validity degrades across the stages of these pipelines.<n>We present a three-layer compounding validity model that captures multiplicative degradation across task generation, human-simulator calibration, and automated judgment.
  arXiv  Detail & Related papers  (2026-08-01T17:50:12Z)
• Cascading Hallucination in Agentic RAG: The CHARM Framework for Detection and Mitigation [0.0]
  We introduce CHARM, an architectural framework for detecting and interrupting error propagation in multi-step reasoning pipelines.<n> CHARM comprises four components - stage-level fact verification, cross-stage consistency tracking, confidence propagation monitoring, and cascade resolution triggering.<n>We evaluate CHARM on HotpotQA, MuSiQue, 2WikiMultiHopQA, and a custom adversarial dataset across LangChain agentic pipeline configurations.
  arXiv  Detail & Related papers  (2026-06-03T04:33:47Z)
• Step-wise Rubric Rewards for LLM Reasoning [72.17879367869503]
  Reinforcement Learning with Verifiable Rewards (RLVR) is widely used to improve reasoning in large language models.<n>We find 18.2% of steps in correct responses are wrong yet positively rewarded.<n>Across six mathematical reasoning benchmarks, SRaR improves average accuracy over RaR by 3.57 points.
  arXiv  Detail & Related papers  (2026-05-17T07:08:14Z)
• When Agents Look the Same: Quantifying Distillation-Induced Similarity in Tool-Use Behaviors [66.18091962164219]
  Existing metrics fail to distinguish mandatory behaviors required for task success from non-mandatory patterns that reflect a model's autonomous preferences.<n>We propose two complementary metrics to isolate non-mandatory behavioral patterns: textbfResponse Pattern Similarity (RPS) for verbal alignment and textbfAction Graph Similarity (AGS) for tool-use habits modeled as directed graphs.
  arXiv  Detail & Related papers  (2026-04-23T03:48:56Z)
• ContraPrompt: Contrastive Prompt Optimization via Dyadic Reasoning Trace Analysis [0.6372261626436676]
  We introduce ContraPrompt, built on the observation that when a model fails but succeeds on a retry with feedback, the difference constitutes an optimization signal.<n>Unlike prior contrastive methods, we compare complete intermediate reasoning processes.<n>ContraPrompt beats GEPA on 11, ties on 41, and loses on 1 at equal budget.
  arXiv  Detail & Related papers  (2026-04-20T08:17:15Z)
• Claw-Eval: Toward Trustworthy Evaluation of Autonomous Agents [66.97968363332465]
  We introduce Claw-Eval, an end-to-end evaluation suite addressing all three gaps in agent benchmarks.<n>Claw-Eval comprises 300 human-verified tasks spanning 9 categories across three groups.<n>Every agent action is recorded through three independent evidence channels.
  arXiv  Detail & Related papers  (2026-04-07T17:43:18Z)
• APEX-EM: Non-Parametric Online Learning for Autonomous Agents via Structured Procedural-Episodic Experience Replay [7.370176470430802]
  LLM-based autonomous agents lack persistent procedural memory.<n>We present APEX-EM, a non-parametric online learning framework that accumulates, retrieves, and reuses structured procedural plans.
  arXiv  Detail & Related papers  (2026-03-31T00:24:56Z)
• TRAJEVAL: Decomposing Code Agent Trajectories for Fine-Grained Diagnosis [23.834704102474927]
  Code agents can resolve GitHub issues, yet when they fail, current evaluation provides no visibility into where or why.<n>We introduce TRAJEVAL, a diagnostic framework that decomposes agent trajectories into three interpretable stages.<n>We validate that these diagnostics are predictive, achieving model-level Pass@1 prediction within 0.87-2.1% MAE.
  arXiv  Detail & Related papers  (2026-03-25T05:27:03Z)
• AgentAssay: Token-Efficient Regression Testing for Non-Deterministic AI Agent Workflows [0.0]
  AgentAssay is the first token-efficient framework for regression testing non-deterministic AI agents.<n>It achieves 78-100% cost reduction while maintaining rigorous statistical guarantees.
  arXiv  Detail & Related papers  (2026-03-03T04:59:25Z)
• Solver-in-the-Loop: MDP-Based Benchmarks for Self-Correction and Behavioral Rationality in Operations Research [19.31559944205485]
  Operations Research practitioners routinely debug infeasible models through an iterative process.<n>We introduce two benchmarks that place the textbfsolver in the evaluation loop<n>We find that domain-specific RLVR training enables an 8B model to surpass frontier APIs.
  arXiv  Detail & Related papers  (2026-01-28T20:02:44Z)
• Towards a Science of Scaling Agent Systems [79.64446272302287]
  We formalize a definition for agent evaluation and characterize scaling laws as the interplay between agent quantity, coordination structure, modelic, and task properties.<n>We derive a predictive model using coordination metrics, that cross-validated R2=0, enabling prediction on unseen task domains.<n>We identify three effects: (1) a tool-coordination trade-off: under fixed computational budgets, tool-heavy tasks suffer disproportionately from multi-agent overhead, and (2) a capability saturation: coordination yields diminishing or negative returns once single-agent baselines exceed 45%.
  arXiv  Detail & Related papers  (2025-12-09T06:52:21Z)
• Metacognitive Self-Correction for Multi-Agent System via Prototype-Guided Next-Execution Reconstruction [58.51530390018909]
  Large Language Model based multi-agent systems excel at collaborative problem solving but remain brittle to cascading errors.<n>We present MASC, a metacognitive framework that endows MAS with real-time, unsupervised, step-level error detection and self-correction.
  arXiv  Detail & Related papers  (2025-10-16T05:35:37Z)
• Eigen-1: Adaptive Multi-Agent Refinement with Monitor-Based RAG for Scientific Reasoning [53.45095336430027]
  We develop a unified framework that combines implicit retrieval and structured collaboration.<n>On Humanity's Last Exam (HLE) Bio/Chem Gold, our framework achieves 48.3% accuracy.<n>Results on SuperGPQA and TRQA confirm robustness across domains.
  arXiv  Detail & Related papers  (2025-09-25T14:05:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.