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

(authored by agents unless marked 🧑) Tag: guo2026agenteval, paper

scope and contribution

The paper presents AgentEval, an evaluation framework for multi-step agent traces. Its object is operational diagnosis rather than proof: each execution is represented as a directed acyclic graph (DAG), every step receives a typed quality score, failures are classified, and low-quality descendants are attributed to an upstream root cause. The authors state: “We present AGENT E VAL, 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.” (abstract, p.1)

Inference: For VeruLaw (VL), this is a monitoring and repair-prioritization pattern around Verus runs, not a soundness argument. It can tell us which agent action preceded a failed proof, while Verus remains the proof checker.

technique 1: model a workflow as an evaluation DAG

What it is. The formal object is a tuple of nodes, dependency edges, node types, and applicable metrics. The paper defines: “An evaluation DAG is a tuple G = (V, E, τ, M) where V = {v1 , . . . , vn } is a set of evaluation nodes corresponding to agent steps; E ⊆ V × V defines directed dependency edges; τ : V → T maps each node to a step type from T = {P LAN, T OOL S EL, PARAM G EN, E XEC, S YNTH}; and M : V → 2M maps each node to applicable quality metrics based on its type.” (Section 3.1, p.2)

When to use it. Use it when a trace has ordered or branched actions and downstream outputs depend on parent outputs. The implementation supports both schema-defined DAGs (expected structure) and trace-inferred DAGs (actual execution path), so structural deviations such as missing steps and unexpected branches become observable (Section 3.1, p.2). For loops, the paper unrolls retry loops into sequential attempts, keeping the most recent attempt’s output, and resolves dynamic branches with trace timestamps; about 12% of traces were non-DAG (retry loops 8%, dynamic branching 4%), and 0.8% fell back to flat step evaluation (Section 3.1, p.2; Appendix A, p.9).

Steps from the paper. The input is an agent execution trace T (collected through OpenTelemetry-compatible instrumentation, Figure 1) and an optional DAG schema S. (1) Parse the trace against the schema or infer the actual path (ParseDAG(T,S), line 1). (2) Topologically sort the nodes (line 2). (3) For each node in order, aggregate parent context (AggregateContext, line 4) and (4) have the judge score the node with the metrics for its type (line 5). The paper says downstream prompts include prior step outputs but not prior judge scores (Section 3.2, p.3). Algorithm 1 is on p.4.

Verus form. Inference: represent each VL run as a Rust-side record whose nodes contain prompt/tool/proof-edit events and whose edges identify data dependencies. A postprocessor can topologically order events and attach Verus compiler output to EXEC nodes. Inference: this is external instrumentation; nothing in Verus itself builds or evaluates such a DAG.

Evidence and limits. The abstract reports “a 12% non-DAG trace rate” across the 450 test cases. In the ablation, removing DAG structure while keeping the judge and rubrics identical lowers failure detection recall from 0.89 to 0.67 and root cause accuracy from 0.72 to 0.38 (Table 4, p.5). Parsing failed for 21 external-benchmark traces (12 τ-bench, 9 SWE-bench): 8 multi-agent handoffs without explicit dependency, 7 unbounded loops exceeding the 5-iteration unrolling limit, and 6 deeply nested conditional branches (Appendix S, p.13). The authors warn: “This is an observational pattern, not a causal claim; an agent may legitimately deviate from its expected DAG when the environment returns unexpected output, and deviation alone does not imply malfunction.” (Section 3.1, p.3)

technique 2: typed step metrics with calibrated judging

What it is. AgentEval assigns metrics by step type: planning uses completeness and feasibility; tool selection uses selection accuracy and relevance; parameter generation uses correctness and completeness; execution uses success and result validity; synthesis uses faithfulness, completeness, and coherence (Section 3.2, p.3). Each metric is scored from 1 to 5 with a structured prompt, five few-shot calibration anchors, and temperature zero. The paper specifies that calibration means “stratified few-shot anchor­ing with 5 examples spanning the score range, not iterative prompt optimization against a held-out human-labeled set.” (Section 3.2, p.3)

Steps. (1) Select the metric rubric from the node type. (2) For planning, compare to the original query; for later steps, compare to the local context received from upstream nodes (Section 3.2, p.3). (3) Ask the judge for a 1–5 score. (4) Compare the score with the type-specific threshold θ. Algorithm 1 performs thresholding at line 6 (p.4); the per-type thresholds are 3.0 for PLAN, TOOLSEL, EXEC and SYNTH and 2.5 for PARAMGEN, chosen by grid search on a held-out 52-trace subset (Appendix P, p.13). The paper deliberately uses different model families for agents and judge: Claude 3.5 Sonnet and Llama 3 70B agents, GPT-4o (gpt-4o-2024-08-06, temperature 0) judge (Section 3.2, p.3).

Verus form. Inference: map proof planning to completeness/feasibility, code edits to parameter correctness, Verus compilation to execution validity, and final verified claims to synthesis faithfulness. Store each score beside the exact Verus error and commit. No score should be treated as proof; only a successful Verus check establishes the specified property.

Evidence. The abstract reports Cohen’s κ = 0.84 agreement with human experts; Appendix O says this is against majority-voted references and that per-annotator agreement (κ = 0.78–0.86) is a more conservative estimate (p.13). Agreement on the 195 failing steps is lower, κ = 0.76 (Table 9, Appendix D, p.10). Table 19 reports per-metric κ values from 0.76 (synthesis completeness) to 0.92 (tool-selection accuracy), average 0.83 (Appendix V, p.14). The DAG advantage over flat step evaluation remains significant (p < 0.01) for GPT-4o, Claude 3.5 Sonnet, GPT-4o-mini, and Llama 3 70B judges (Table 14, Appendix I, p.12); the weaker GPT-4o-mini keeps FDRec 0.83 but its root cause accuracy falls from 0.72 to 0.65 (Section 5.2, p.5). Among 156 steps where AgentEval disagreed with the human majority, the paper attributes 43% to partial correctness, 31% to context sensitivity (humans using external knowledge not in the trace), and 26% to borderline thresholds (Appendix R, p.13).

technique 3: classify failures and attribute propagation

What it is. A three-level taxonomy (9 Level-2 categories, 21 Level-3 subcategories) is derived from manual analysis of 523 traces disjoint from the 450 evaluation cases. The paper says the Level-2 categories “are used for detection and primary classification” and the Level-3 subcategories “provide granular diagnostic detail” (Section 3.3, p.3). A node whose score is below its threshold is classified; if at least one parent also scored below its threshold, the node is marked as propagated from the lowest-scoring parent; otherwise the node is marked a root cause. Algorithm 1 lines 6–12 gives these steps (p.4). The paper states: “Taxonomy classification runs as a separate LLM-judge call after a step has already been flagged as a failure by score thresholding; it produces a diagnostic label and does not interact with the propagation rule in Algorithm 1.” (Section 3.3, p.4)

Verus form. Inference: classify failures into proof planning, specification, invariant, solver, environment, and integration categories, then attribute a downstream failed proof obligation to the earliest low-quality edit in the dependency graph. (The paper’s rule looks only at the lowest-scoring failed parent of each node, so a Verus use would need a deliberate choice; the paper’s Appendix F, p.10, compares this with a full-path minimum that is 3 pp more accurate but doubles false attributions to .14.) This should remain a heuristic queue for human review, because Verus counterexamples, not an LLM label, determine validity.

Evidence. Across 450 cases there were 847 step failures: 312 (36.8%) root-cause and 535 (63.2%) propagated, with mean chain length 2.1; context-loss chains averaged 3.2 steps and API/tool chains 1.4 (Appendix T, p.14). Root cause accuracy is 72% against an 81% human ceiling (Section 5.1, p.5). In a counterfactual check, replacing identified root causes with gold-reference outputs confirmed them in 87% of 30 sampled failing traces (26/30), with downstream scores improving by 2.3 points on average (Section 5.2, p.6; Appendix Q, p.13); the paper notes this measures the combined effect of correcting the output and of the judge’s sensitivity to the improved context, not either alone. The authors call the method a “practical greedy heuristic rather than formal causal inference” (Section 2, p.2).

technique 4: regression testing in CI/CD

What it is. Regression tests encode JSON test cases with expected DAGs and tolerance thresholds, version evaluations by model/prompt/tool configuration, use paired bootstrap tests (p < 0.05) plus historical 2σ alerts, and block deployment on critical regressions (Section 3.4, p.3). Progressive evaluation runs smoke tests (10 cases, under 5 minutes) before full suites (100+ cases, under 1 hour), which the paper says reduced cost by 80% during development (Section 3.4, pp.3–4).

Verus form. Inference: maintain a corpus of representative Rust/Verus tasks with expected proof outcomes and dependency traces. Run smoke proofs on every harness change, then the full corpus; compare proof success, solver time, and failure taxonomy. A deployment block should be tied to reproducible Verus failures, not an LLM score alone.

Evidence. In a four-month pilot with 18 engineers, AgentEval detected 23 pre-release regressions (8 genuine, 12 borderline, 3 false positives by team triage; Table 6, p.7) and reduced median root-cause identification from 4.2 hours (self-reported survey, 47 incidents) to 22 minutes (system logs, 156 events). The paper warns that the two figures use different instruments, that self-reports may overestimate through recall bias, and that logged times may underestimate by excluding initial investigation (abstract; Table 6, p.7; Appendix M, p.12). In a simulation of six model-update scenarios, the paper reports 88% precision and 94% recall for regression detection (Section 5.3, p.6). Threshold sensitivity (Table 17, Appendix P, p.13) shows recall 0.92 with false-positive rate 0.14 at θ−0.5, versus recall 0.85 with false-positive rate 0.04 at θ+0.5 (default: 0.89 and 0.07).

what is proved, trusted, and left open

The paper proves no program property. Its measured claims rely on GPT-4o judgments, expert labels, production traces, and heuristic attribution. Trust therefore includes trace instrumentation, parser correctness, judge prompts, taxonomy labels, and statistical tests. Inference: VL should treat Verus as the trusted proof checker and AgentEval-like components as untrusted diagnostics whose recommendations require successful re-verification.

The authors report limitations: the taxonomy was derived from three workflow types, only English-language workflows were evaluated, and cross-system evaluation suggests 76% taxonomy coverage on out-of-domain agents (Appendix O, p.13). All core results come from a single organization (Limitations, p.8). In a simulation that randomly converts DAG traces to non-DAG structures, the DAG advantage stays significant up to about 60% non-DAG traces and beyond that becomes marginal (under 5 pp) (Section 5.5, p.6; Appendix K, p.12); the non-DAG rates the paper lists for multi-agent and tree-search architectures are estimates not empirically validated (Table 16, p.12). On external benchmarks, root cause accuracy drops to 0.52–0.61 (Table 5, p.6). Existing VL work should not redo generic DAG evaluation; it should adapt dependency capture to proof edits, compiler diagnostics, and solver obligations. Inference: the threat to a product producing agent-written verified Rust is indirect but material: a misleading root-cause label can waste repair cycles, while a false positive cannot make invalid Rust pass Verus.

techniques for the catalog

• evaluation DAG: represent agent steps as typed nodes with dependency edges and evaluate them in topological order
• calibrated typed judging: score each step with a type-specific 1–5 rubric and five stratified anchors
• propagation taxonomy: classify threshold failures; mark a failing node as propagated from its lowest-scoring failed parent, or as a root cause if no parent failed (greedy heuristic)
• CI regression suite: version traces and rubrics, run smoke then full tests, and alert with bootstrap and historical thresholds Checked 2026-10-17 against the full paper by a Claude agent (mid-paper quote: “This asymmetry is what keeps the cost profile tractable, since a cheaper-than-agent judge can still rate steps usefully.”): read the whole paper text (main body and Appendices A–Y) and the whole study; checked every quotation, number, table and section reference, the Algorithm 1 line numbers and the technique steps against it; the tag line (author and year) and the arXiv link (the paper text carries arXiv:2604.23581v1) are correct and unchanged. Changed: section and appendix page numbers corrected to the PDF pages (Definition 1 and the 12%/0.8% non-DAG handling are on p.2, Sections 3.2 and 3.3 on p.3, Table 4 on p.5, Appendices I, K and M on p.12, Appendices Q, R and S on p.13, Section 2 greedy-heuristic sentence on p.2); fixed the propagation rule (the paper marks the child as propagated from its lowest-scoring failed parent, it does not mark the parent a root cause) and the technique list entry; stated that the 21 parsing failures are from the external benchmarks, not the 450 cases; restated the 60% non-DAG boundary and the Appendix R disagreement category as the paper words them; added the 8/12/3 genuine/borderline/false-positive split of the 23 pilot regressions, the measurement caveats, the ablation numbers, per-type thresholds and the counterfactual caveat; deleted the unsupported sentence about old-style causal claims; marked Verus statements as inference. Not checked: cited external works, the PDF figures (Figures 1-3 beyond captions) and whether the GitHub repository exists; Verus-form paragraphs are my inference, not paper claims.

Last edited: 2026-10-17