PaperlayerView exact revision on arXiv

Source-linked AI summary

EDGE: Error Dependency Graph-Guided Multi-Error Attribution in Multi-Agent LLM Systems

Jun Hou, Priya Pitre, Yi Fang, Xuan Wang

arXiv:2609.01360v1cs.AI

TL;DR

Existing attribution methods generally focus on a single error and do not explicitly model dependencies among multiple errors in agent failures. EDGE constructs and validates an error dependency graph, uses it in a two-stage detector, and improves category-level multi-error attribution across most evaluated models and settings on TRAIL and MAST. The validated subgraph also supports explanation and repair analysis, while graph-based localization remains more limited.

  • Problem

    Existing attribution methods usually target a single error, step, or root cause rather than modeling dependencies among multiple errors.

  • Method

    EDGE constructs an error dependency graph from observed events, validates edges through counterfactual rollout, and uses the graph to guide a two-stage LLM-as-judge detector.

  • Results

    EDGE improves category-level multi-error attribution across most evaluated models and settings on TRAIL and MAST, spanning span-level and trace-level benchmarks.

  • Takeaways & Limitations

    Dependency structure provides useful diagnostic support beyond isolated label prediction and enables more explainable debugging and repair prioritization.

  • Takeaways & Limitations

    The graph contains aggregate category-level dependencies rather than trace-specific labels, spans, or task answers, and localization gains are smaller than detection gains.

Abstract

from arXiv · show

Large language model (LLM) agent failures often contain multiple related errors rather than a single mistake. Existing attribution methods usually identify a responsible agent, step, or root cause, but do not explicitly model dependency between errors. We introduce EDGE, an Error Dependency Graph-guided multi-Error attribution framework. EDGE constructs an error dependency graph from observed error events and validates a reliable causal subset through counterfactual rollout. The inference graph guides a two-stage LLM-as-judge detector for error attribution, and the intervention-validated subgraph provides a more reliable basis for explanation and repair analysis. Experiments on TRAIL and MAST show that EDGE improves category-level multi-error attribution across most evaluated models and settings. Experiments with adapted Who&When-style prompts show that the graph helps across prompting strategies. These results suggest that dependency structure is a useful diagnostic prior for agent failures beyond isolated root-cause prediction.

1 Introduction

LLM agent failures often contain multiple structurally related errors, but existing attribution methods largely treat errors as isolated targets. EDGE frames attribution as dependency-aware diagnosis, using an error dependency graph and counterfactual validation to guide detection and explanation.

  • Existing trace-level attribution methods identify responsible steps or errors but do not provide full step-level multi-error annotation.
  • Errors in failed traces can act as upstream triggers, downstream effects, or parallel symptoms, motivating dependency modeling.
  • EDGE constructs an error dependency graph from observed error events using within-trace ordering and cross-trace regularity.
  • A two-stage detector first predicts an initial error set, then verifies downstream errors suggested by the graph.
  • EDGE uses observational edges to broaden attribution coverage and intervention-validated edges to support more reliable explanation and repair analysis.

2 Related Work

Prior agent-failure attribution methods use trajectory reasoning, hierarchical context, adjudication, causal graphs, or constraint-based evidence, but primarily target a single decisive error or local root cause. Related event-progression work learns temporal or causal structure from sparse event data.

  • Who&When formulates agent attribution as direct reasoning over execution trajectories.
  • Other attribution methods add hierarchical context, iterative adjudication, or structured causal representations to LLM-based diagnosis.
  • CDC-MAS, CHIEF, and AgentRx combine causal inference, counterfactual screening, or constraint-based evidence with LLM judgment for diagnosis.
  • These attribution methods still primarily target a single decisive error, critical step, or local root cause.
  • Sparse event-progression research learns temporal influence and causal structure from timestamped or accumulating event data.

3 Method

EDGE constructs an error-dependency graph from annotated agent traces, validates candidate propagation edges through counterfactual rollout, and uses the resulting structure to guide two-stage multi-error attribution. The inference graph preserves intervention-validated causal edges while adding score-filtered observational edges to broaden downstream error detection.

  • Problem setup: EDGE formalizes attribution as predicting category-location pairs from span-ordered traces annotated with multi-error events.Each error event records a category and the span where it first emerges; execution order supplies temporal information for graph construction.
  • Observational graph construction: The method builds observational and causal-candidate graphs over error categories using temporal precedence, probability raising, and CAPRI-style score pruning.Suppes screening identifies candidate propagation edges, while regularized likelihood pruning produces a sparser DAG-based causal-candidate graph.
  • Intervention-based graph validation: Counterfactual rollout validates candidate edges by repairing the upstream error, holding tool outputs fixed, and measuring whether the downstream error remains.Edges are retained in the validated graph when their estimated downstream reduction effect exceeds the validation threshold.
  • Graph-guided error detection: A two-stage LLM-as-judge detector first predicts errors using full-graph context, then verifies downstream categories reachable from detected source categories.Stage 2 receives a trace-specific subset of graph edges selected by the graph-injection threshold.
  • Inference graph selection: The inference graph unions score-filtered observational edges with all intervention-validated causal edges, retaining the causal anchor while recovering correlations that interventions cannot validate reliably.Validated edges use their reduction effect as propagation weight, whereas observational edges use their Suppes geometric-mean score.

4 Experiments

EDGE is evaluated on span-level TRAIL and trace-level MAST attribution using fixed taxonomy-level graphs, dynamic two-stage graph injection, and comparisons against static, random, causal-only, and held-out alternatives. Across models and prompting strategies, graph guidance generally improves category attribution and supports intervention-backed repair analysis, although some gains trade accuracy for recall and long-context localization remains difficult.

  • Experimental Setup: EDGE evaluates span-level multi-error attribution on TRAIL and trace-level multi-label attribution on MAST using eleven open- and closed-weight backbones.TRAIL requires category and location prediction, whereas MAST evaluates trace-level classification across 13 categories.
  • Main Results: 42.13 F1 on TRAIL-GAIA and 38.97 on TRAIL-SWE-Bench are Gemini-2.5-Pro's strongest reported results.Open-weight models gain up to +21 F1 on SWE-Bench, while exact localization on long-context SWE-Bench remains difficult.
  • Main Results: 22.87→29.96 F1 is GPT-4o's MAST improvement, while seven of eight backbones trade −0.33 to −3.74 accuracy for +3.09 to +17.52 recall.The paper recommends reading accuracy alongside recall because only 30.5% of binary category decisions are positive.
  • Graph-Richness Ablation: Random-12 underperforms the inference graph on 4 of 5 open-weight backbones, and Gτ at τ=0.35 reaches the F1 peak on 4 of 5.Gemma-27B is the exception, where the causal-only graph wins F1.
  • Static Graph Guidance Ablation: EDGE outperforms static graph guidance on 14 of 15 backbone cells, supporting trace-conditioned two-stage consumption as the operational lever.Static guidance helps some cells but degrades others, including −10.8 F1 on GPT-oss-20B TRAIL-GAIA and −3.2 on Qwen MAST.
  • Held-out Graph Validation: Held-out graph validation improves weighted-F1 in all four representative cells, with gains of +8.40, +2.40, +1.91, and +12.41 across TRAIL and MAST.The graph is rebuilt from training traces and evaluated only on untouched held-out traces, indicating transfer beyond the construction corpus.
  • Who&When-Style Adaptation: Graph guidance benefits both Who&When-style prompting strategies across TRAIL, while a graph-guided variant achieves the best MAST F1 across all shown model blocks.STEP-BY-STEP+GRAPH yields uniform SWE-Bench gains, whereas GAIA shows minor volatility for GPT-oss-20B.
  • Causal Graphs as Explanatory Artifacts: Intervention-validated GV exposes propagation chains for explanation and repair, including Formatting Errors → Context Handling Failures and Action-Reasoning Mismatch → Premature Termination.The causal graph is retained as a trustworthy propagation structure rather than merely a predictive context block.

5 Conclusion

EDGE constructs and exploits an error dependency graph for multi-error attribution in LLM agent traces. Across TRAIL and MAST, its inference graph improves category-level attribution and supports explainable debugging and upstream repair prioritization.

  • EDGE is a graph-guided framework for multi-error attribution in LLM agent traces.
  • EDGE is taxonomy-agnostic and can be rerun with any error taxonomy containing observed error events.
  • Across TRAIL and MAST, the inference graph improves category-level multi-error attribution in both span-level and trace-level settings.
  • Dependency structure supports more explainable debugging, upstream repair prioritization, and more reliable improvement of long-horizon agent systems.

Limitations

EDGE’s evaluation is limited to taxonomy-level dependency-guided attribution, with graph, annotation, intervention, reproducibility, and deployment-scope constraints. These limitations affect causal interpretation, localization, transferability, and future repair-loop evaluation.

  • Scope: EDGE remains a taxonomy-level attribution method because its fixed graph contains aggregate category dependencies rather than trace-specific labels, spans, or task answers.The graph is constructed from the full annotated corpus because multi-error annotations are scarce and have low per-category support.
  • Localization: Category co-occurrence improves error-event detection more than trajectory localization, whose gains stay close to flat on the long-context SWE-Bench split.This limitation follows from estimating the graph from category co-occurrence rather than trace-localized information.
  • Causal interpretation: The inference graph broadens coverage with observational edges, but these edges may overclaim propagation and may not remain reliable under distribution shift.The intervention-validated graph is the more reliable structure for explanation and repair analysis.
  • Intervention validation: Intervention effects reflect propagation along the agent’s reasoning path because tool outputs are held fixed, excluding mediation through downstream tool re-execution.Validation is also limited by the number of co-occurring traces available for each candidate edge.
  • Annotation quality: Automatically produced, not fully human-validated MAST event annotations may introduce noisy positions that affect temporal-priority estimates and the inferred graph.The authors identify fully human-validated event annotations as a way to strengthen future evaluation.
  • Deployment and future work: EDGE applies graph guidance uniformly, while confidence- or complexity-based gating and large-scale repair-loop re-execution remain future work.Graph-guided outputs should be treated as diagnostic aids with human review, especially in high-stakes deployments.
  • Reproducibility: Reported numbers are single-run point estimates, and LLM inference nondeterminism means exact replication of the paper’s values is not guaranteed.The code and inference scripts are available, but the authors do not guarantee identical numerical results.

Ethical Considerations

The study uses publicly available benchmarks without new human-subject or private-user data. AI assistants supported implementation and manuscript preparation, with generated content reviewed and revised by the authors.

  • Data and evaluation: The evaluation uses publicly available benchmarks under their original terms and does not collect new human-subject data or use private user data.Some pipeline components rely on LLM judgments, which may introduce annotation noise or model bias.
  • AI assistance: AI assistants were used for implementation and manuscript preparation, including table LaTeX and text refinement, and authors reviewed and revised the generated content.The stated uses include generating LaTeX code for tables and refining author-written text.

A.1 Notation Table

The notation table defines EDGE’s graphs, trace-level variables, and scoring thresholds. The symbols distinguish observational hypotheses, causal validation, inference-graph selection, and event timing.

  • Graphs and edge sets: GS is the observational correlation graph, GC is the CAPRI-pruned causal-candidate DAG, GV is the intervention-validated causal anchor, and Gτ is the detector’s inference graph.Gτ unions GV with score-filtered observational edges from GS, while GV is used for explanation-oriented analysis.
  • Sets and trace-level quantities: C denotes the error taxonomy, T the trace corpus, TA≺B traces where A precedes B, XA(T) event occurrence, and tA(T) A’s first-emergence index.XA(T) is binary, indicating whether category A occurs in trace T.
  • Scores and thresholds: wS(A, B) measures observational propagation, ∆(A→B) measures controlled direct effect, and τ, τGI, and τval govern graph inclusion and Stage-2 exposure.τ thresholds observational edges entering Gτ; τGI thresholds downstream hypotheses exposed in Stage 2; τval thresholds causal-edge validation.

A.2 Causal Graph Construction Details

EDGE constructs observational and causal-candidate graphs from within-trace event order and probability raising, prunes candidates with CAPRI, and validates selected edges by intervention. The resulting graph stages differ across TRAIL and MAST because their taxonomies and corpus support differ.

  • Temporal screening: Within-trace span annotations allow EDGE to estimate temporal priority directly from event order and aggregate it across traces.This adapts Suppes screening to event data rather than relying on marginal occurrence frequency as a temporal-priority surrogate.
  • Temporal screening: Tied events count as category occurrences but do not support strict temporal direction.The first-event index identifies the first span where each category emerges.
  • Causal-candidate construction: CAPRI prunes the Suppes-screened graph by an AIC-style likelihood score using hill-climbing over edge addition, removal, and reversal while enforcing acyclicity.The optimization operates over an admissible edge family and minimizes a regularized score balancing likelihood and graph complexity.
  • Graph yields: TRAIL skips bootstrap and shuffle controls because of small sample size, whereas MAST uses 100 bootstrap runs and 50 shuffles.These controls are part of the graph-construction reporting configuration for MAST.
  • Graph yields: MAST retains 23 causal-candidate edges versus 13 for TRAIL before intervention validation under the production AIC configuration.MAST’s flat 13-code taxonomy and 393-trace corpus provide more co-occurrence support than TRAIL’s 19 hierarchical leaves.
  • Intervention validation: Intervention eligibility requires both categories to occur and the source’s first event to strictly precede the target’s first event.This ordering restricts experiments so downstream changes can be attributed to intervention on the source rather than baseline ordering.
  • Intervention validation: TRAIL covers 19 source-error categories and MAST covers 13 categories, with category-specific patch libraries defining intervention sides, repair instructions, forbidden actions, and postchecks.The library supports replacing span outputs or inputs depending on the source category and benchmark taxonomy.

TRAIL patch library (causal/patch/patch_library.json)

The TRAIL patch library defines error-specific repairs, forbidden actions, and postchecks for formatting, task identification, retrieval, and resource-use failures.

  • Formatting Errors: Formatting repairs make the smallest structural edit needed to satisfy explicit format requirements while preserving semantic content.Required markers may be inserted exactly when explicitly grounded; new factual content, tools, and unsupported reasoning are forbidden.
  • Incorrect Problem Identification: Incorrect problem identification repairs rewrite the local instruction or thought around the actual task objective and immediate subgoal.The repair narrows local scope, preserves useful constraints, and avoids fabricating facts or pre-answering the task.
  • Poor Information Retrieval: Poor information retrieval repairs redirect queries or plan steps toward task-relevant information while retaining explicit source and time constraints.The library forbids injecting answers, fabricating evidence, or adding unrelated exploratory searches.
  • Resource Abuse: Resource-abuse repairs identify redundant calls, use already-known results, and stop once the minimal completion condition is met.The relevant slots are the immediate subgoal, repeated action, available result, and stopping criterion.

MAST patch library (causal_graph/causal_valid/patch_library.json)

The MAST patch library covers task and role violations, repeated steps, lost conversation history, termination errors, and conversation resets through targeted span replacements.

  • Disobey Task Specification: Disobey Task Specification repairs rewrite step content to comply with stated task constraints while preserving valid reasoning and the solution approach.The patched step should remove the violated constraint without fabricating requirements or changing the approach unnecessarily.
  • Disobey Role Specification: Disobey Role Specification repairs adjust role-violating behavior while preserving the agent’s goal, task objective, and task-relevant content.The library identifies the violated role requirement and the behavior consistent with the assigned role.
  • Step Repetition: Step Repetition repairs replace a redundant step with acknowledgment of the prior result and a forward move.The procedure identifies both the repeated step and the result already obtained, while forbidding fabricated results and skipped required steps.
  • Loss of Conversation History: Loss of Conversation History repairs explicitly incorporate relevant prior context without fabricating or introducing information absent from that context.The patch identifies the lost context and the required reference for the current step.
  • Unaware of Termination Conditions: Unaware of Termination Conditions repairs either terminate after a valid stopping point or continue toward the required completion criterion.The repair must not fabricate completion criteria or alter the task goal.
  • Conversation Reset: Conversation Reset patches replace content that discarded prior context or progress, using replace_step_content as the default patch side.The library records lost progress as a key repair slot.

Judge A user template — output-side patch (TRAIL)

The TRAIL output-side judge compares original and patched spans to determine whether a specified error criterion has been eliminated in the patched content.

  • Judge inputs: The judge receives the source error type, description, evidence, original span, and patched span as comparison inputs.It focuses on the patched content itself rather than requiring a particular output beyond the evaluated error criterion.
  • Judge output: The judge returns JSON containing a Boolean resolution decision, a confidence score from 0 to 1, and an evidence excerpt.The required response format is JSON only.

Judge A user template — input-side patch (TRAIL)

The TRAIL input-side judge evaluates whether patching removes or corrects the context causing an error, without requiring the patched input to produce correct output behavior.

  • Input-side intervention: The intervention removes or corrects error-causing context so the LLM has better information going forward.The comparison uses original and patched message histories and focuses on the specific pattern described in the error evidence or description.
  • Resolution criterion: The judge checks whether the error pattern is absent or corrected in the patched context compared with the original.Because the patch modifies input, the judge must not require the patched input to contain the correct output behavior.
  • Downstream effects: For verified interventions, Judge B assigns downstream effect labels, with only disappeared contributing positively to ∆(A →B).The labels distinguish removal, partial reduction, no effect, negative side effects, and uninformative cases.

Judge B (effect evaluator) system prompt (TRAIL)

Judge B evaluates whether a downstream error changes after intervening on a source error, then aggregates validated effects into the causal graph used by EDGE’s detector. The appendix also contrasts EDGE’s trace-specific two-stage use with static graph guidance and documents benchmark-specific intervention yields and prompting adaptations.

  • Judge B (effect evaluator) system prompt (TRAIL): Judge B compares baseline and counterfactual trace suffixes after locally patching source error A to assess downstream error type B.Its inputs include the target definition, original and rerun suffixes, and onset references.
  • Judge B (effect evaluator) system prompt (TRAIL): Effect labels record whether B disappeared, was delayed, unchanged, earlier, weakened, strengthened, emerged, or was not observable after intervention.The labels distinguish removal, timing, severity, introduction, and unassessable downstream effects.
  • Judge B user template (TRAIL and MAST share this structure): For each candidate edge A→B, EDGE reduces Judge B’s labels to a downstream-presence indicator and computes an averaged Boolean risk-difference effect statistic.The statistic is evaluated over verified interventions, while only traces whose source error is judged resolved contribute to the validated relation.
  • Judge B user template (TRAIL and MAST share this structure): 12/13 (92.3%) of TRAIL candidate-to-validated edges passed the rule, compared with 11/23 (47.8%) on MAST.TRAIL’s live reruns yielded disappeared in 57.5% of trials, whereas MAST’s simulated continuations were dominated by not_observable at approximately 70%.
  • Judge B user template (TRAIL and MAST share this structure): Implementation uses GPT-4o for patching and judging, o3-mini for TRAIL live replay, and LLM-simulated continuations for recorded MAST traces.The counterfactual method differs because TRAIL can be replayed live while MAST consists of recorded multi-agent conversations.
  • A.3 Step Annotation Coverage: MAST’s trace-level annotations are converted into ordered error events by locating each category’s first occurrence.The appendix reports step-annotation coverage separately, with 82.0% overall coverage and a pipeline-designed false-alarm rate of 0.
  • A.4 Detection Pipeline and +CG Ablation: EDGE’s Stage 2 conditions a targeted judge on Stage-1 errors and trace-specific guidance, then merges predictions with category-level deduplication.The static +CG baseline instead prepends the full edge set to one call; on long traces, irrelevant edges and context consumption can reduce coverage, whereas EDGE filters guidance and verifies propagated hypotheses.
Loading 2609.01360v1…