acceptodds
Under review as a conference paper at ICLR 2027

Training-Free Failure Attribution in Multi-Agent Systems via Structured Trajectory Diagnosis

Abstract

Attributing a multi-agent execution failure requires distinguishing the step that introduced a defect from steps that propagated or repaired it. We present Conditional State Decoding (CSD), a training-free framework that separates local relation assessment from global attribution. A frozen language model grades each step under all four combinations of its source and its own correctness state. An exact tree decoder combines these conditional grades into a complete state explanation on a dependency forest. Diagnostic votes support origin selection, and a failure-consistency gate accepts the decoded attribution when the explanation marks the final output as defective, otherwise returning the vote. On two collections, 80 traces from CORRECT-Error and the complete 126-trace Algorithm-Generated subset of Who&When, CSD reaches 90.0% and 54.0% step accuracy with gpt-5-mini, exceeding the strongest reported voting configurations by 2.50 and 4.76 percentage points. On the 18 accepted Who&When traces, structured predictions correctly attribute 13 cases versus 8 for the same-ballot vote. Analyses over cached responses quantify the gate's contribution and the effect of path restrictions on candidate coverage, linking the final attribution to an inspectable account of error onset, propagation and recovery.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Multi-Agent Systems, Failure Attribution, Large Language Models, Structured Inference

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_wrREOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Conditional State Decoding (CSD), a training-free framework for failure attribution in LLM-based multi-agent systems. It uses a frozen language model to assess four source-to-step correctness relationships (i.e., normal behavior, error onset, propagation, and recovery) and combines these assessments through exact dynamic programming over a dependency forest to identify the earliest error source. Experiments on CORRECT-Error and Who&When evaluate its attribution accuracy against prompting and voting-based baselines, along with analyses of decoding strategies and dependency constraints.

Critical strengths

S1. Structured Approach to Agent Failure Attribution

While I feel that the formulation and evaluation lacks enough rigor, I appreciate the overall approach of moving beyond direct LLM-based error localization toward structured trajectory analysis for agent failure attribution.

Critical weaknesses

W1. Limited Benchmark Coverage and Insufficient Comparison with Existing Methods

The experimental evaluation is limited to two relatively small datasets (80 CORRECT-Error traces and 126 Who&When Algorithm-Generated traces), without considering other Who&When subsets or more recent benchmarks such as AgentRx. Moreover, the comparisons primarily focus on direct prompting and voting-based baselines, omitting stronger recent failure-attribution methods such as AgentRx. Given the relatively modest improvements over the strongest reported voting baselines, the limited benchmark coverage and lack of competitive comparisons make it difficult to establish the effectiveness and generalizability of the proposed method.

W2. Restrictive Structural Assumptions and Unclear Methodological Generality

The proposed method assumes that each execution step has a single principal source and can be represented by a binary correctness state, resulting in four predefined source-to-step relations. However, realistic multi-agent workflows may involve multiple upstream dependencies, concurrent errors, or steps that simultaneously repair one error while introducing another. These structural assumptions may oversimplify complex failure propagation patterns, potentially limiting the method's applicability to diverse agent systems. Furthermore, the dependency forest is extracted using an LLM without direct validation of its accuracy, leaving the robustness of the overall framework to incorrectly inferred dependencies insufficiently examined.

Questions for authors

Q1. Benchmark Selection and Ground-Truth Reliability

The evaluation is limited to 80 CORRECT-Error traces and the 126 Algorithm-Generated traces from Who&When. Why are the other Who&When subsets excluded, and why are more recent benchmarks, such as AgentRx, not considered? Furthermore, given the potential ambiguity of single-step failure attribution, how reliable are the ground-truth labels, and how might alternative valid attributions affect the reported results?

Q2. Significance of Improvements and Comparison with Stronger Baselines

The improvements over the strongest voting baselines are relatively modest, corresponding to only two additional correct predictions on CORRECT-80 and six on Who-AG. Are these improvements statistically significant? Moreover, why are stronger recent failure-attribution methods, such as AgentRx, not included in the comparison?

Q3. Generalizability of the Dependency Representation

CSD assumes that each step has a single principal source and represents its correctness using a binary state, enabling four source-to-step relations. However, realistic multi-agent workflows often involve multiple upstream dependencies, concurrent errors, or steps that simultaneously correct one error and introduce another. How well can this representation capture such scenarios, and to what extent do these structural assumptions limit the applicability of CSD to more complex agent systems?

Q4. Reliability and Impact of Dependency Forest Extraction

The dependency forest is a fundamental component of CSD, yet it is constructed through an LLM-based extraction procedure without direct evaluation of its accuracy. How reliable are the extracted parent-child dependencies? Could the authors evaluate dependency extraction against manually verified relationships and compare attribution performance using automatically extracted versus ground-truth dependency structures to quantify the impact of structural errors?

Reviewer_NE4aOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents Conditional State Decoding (CSD), a training-free method for attributing failures in multi-agent traces. A frozen language model extracts a dependency forest and grades each step for four parent-to-step transitions: normal behavior, error onset, propagation, and recovery. A tree dynamic program finds the best joint assignment of correct and defective states. A consistency gate accepts the earliest decoded onset only when the final output is defective; otherwise CSD falls back to a diagnostic vote. Evaluation uses 80 CORRECT-Error traces and the 126-trace Algorithm-Generated subset of Who&When, with gpt-5-mini-2025-08-07. CSD reports 90.0% and 54.0% step accuracy, versus listed voting baselines of 87.5% and 49.2%. Cached-evidence ablations examine decoder, gate, and candidate coverage.

Critical strengths
  1. CSD makes a useful distinction between a defect's origin and its propagation or recovery. Section 3.3 represents these relations explicitly, while Figure 3 shows how a downstream step can inherit an error even when a sibling branch repairs it.
  2. The inference objective is clearly specified. Equation 2 gives an exact tree dynamic program for a fixed forest, and Appendix A.3 explains the complexity, constraints, and tie-breaking behavior sufficiently to understand what is optimized.
  3. Tables 3 and 8 isolate gate behavior, Table 9 reports response counts and API costs, and Appendix C includes prompts and says reference labels are withheld.
  4. The approach needs no attribution-model training and returns an interpretable state assignment.
Critical weaknesses
  1. The gains over the paper's strongest voting configurations are modest: two correct cases on CORRECT-80 and six on Who-AG (Table 2), corresponding to 2.50 and 4.76 percentage points. There are no confidence intervals, repeated model runs, or paired significance analysis, so it is unclear how stable these margins are.
  2. The model and benchmark scope is narrow. Both collections are small, and all evidence is elicited from one frozen model, gpt-5-mini. In particular, CORRECT-80 has only 80 traces and Who-AG is one subset of one benchmark; these results do not yet establish robustness to different models, agent architectures, or longer traces.
  3. Table 2 compares CSD only to direct diagnosis and voting configurations built from the same model responses. Although the related-work section discusses ECHO and CHIEF, the paper does not provide a comparable evaluation against these structured diagnosis approaches, nor explain how differences in prompt/model access prevent a fair comparison. The core improvement over existing attribution methods therefore remains uncertain.
  4. CSD's key structural input is itself a model-generated principal-source forest (Section 3.2). The paper reports that annotated origins lie in the final-output ancestry for 71/80 and 123/126 traces (Appendix B.4), but does not directly evaluate dependency-edge precision or recall. Since an incorrect forest can make the structured explanation misleading, how often does the extracted graph reflect the actual information dependencies?
  5. The primary numbers depend on collection-specific choices of ballot family, weights, penalties, and readout (Table 6). For CORRECT-80, all transition penalties and vote priors are zero; for Who-AG, the prior and penalties differ. Appendix B.1 lists the final settings but does not establish whether they were fixed without using attribution labels on the evaluated collections. This leaves some risk of benchmark-specific selection.
Questions for authors
  1. Were the Table 6 coefficients and prompt configurations selected without using reference attributions from the evaluation traces? Please describe the selection protocol.
  2. Can you report paired bootstrap intervals or repeated-call variability for the Table 2 differences?
  3. Can you evaluate dependency-forest edges against annotated or human-checked source relations, and show attribution accuracy with an oracle forest?
  4. Can the method be compared with ECHO, CHIEF, or another structured baseline under a shared model and prompt budget?
Reviewer_Fh5wOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

CSD is a training-free method for step-level failure attribution. A frozen gpt-5-mini extracts a dependency forest over the steps and grades each step under all four combinations of its source's state and its own (normal, onset, propagation, recovery). An exact tree decoder turns these grades into a state assignment, with origin selection that can also use a vote prior. If the assignment marks the final output as defective, CSD returns the earliest onset; otherwise it falls back to a diagnostic vote. On 80 CORRECT-Error traces and the 126 Algorithm-Generated traces of Who&When, CSD gets 72/80 and 68/126, 2.50 and 4.76 points above the strongest reported voting configurations, and on the 18 Who&When traces that pass the gate it is correct on 13 versus 8 for the same-ballot vote.

Critical strengths

(1) The modeling idea is concrete and well motivated. When a step faithfully reuses its input, that is normal behavior if the source is correct and propagation if the source is defective, so a single correctness judgment has to commit before the source's state is known. Grading each step under every combination of states and leaving the decision to global inference is a natural way around this. The paper is also clear that the inference algorithm itself is standard and that the task-specific design lies in the conditional state interface, the dependency structure and the failure-aware readout (l.137–138).

(2) The comparisons are transparent about evidence. All decoders reuse the same cached forest, grades and ballots (l.354–355), Table 3 compares against a vote built from exactly the same ballots, and the authors themselves report that on CORRECT-80 the structured predictions are correct on as many gate-pass traces as that vote (42 vs 42 of 47, l.406–407). This transparency is what makes the analysis in my first weakness possible.

Critical weaknesses

(1) The headline gains are not shown to come from structured decoding. Under R1, CSD returns the decoded onset on gate-pass traces and the vote on all others (l.294–303; Algorithm 2, lines 11–14), and Table 3 compares against CSD's own vote with the same ballots and weights (l.382–383, l.396–397, l.403–404). CSD's total is therefore its own vote's total plus the difference on gate-pass traces. On CORRECT-80 that difference is zero (42 vs 42), so CSD's 72/80 is exactly what its ballot configuration (Integrity 8 + Contracts 2, weights 1:2; Table 6) scores by voting alone. That configuration is not a Table 2 baseline, so the +2.50 over the strongest reported vote comes from the choice of ballots. On Who-AG, CSD's own vote would score 8 + 55 = 63 (Tables 3 and 8), already above every reported vote (best 62), and decoding adds five traces; even in the most favorable split (5:0), the exact two-sided McNemar test gives p = 0.0625.

Two other results point the same way. The R2 readout, where every prediction comes from the constrained decoder, reaches 65/126 (l.430–431), two traces above CSD's own vote, and it uses a vote prior with β = 2 (l.701). Under the separately reported R0 configuration, Greedy decoding without the terminal gate already reaches 72/80 and 68/126, the headline numbers (Table 4).

(2) The central idea is not isolated, and the configuration was set on the evaluation collections. No ablation replaces the conditional four-way grades with unconditional per-step grades under the same decoder, so I cannot tell whether the conditional interface, which the paper lists as its first contribution (l.89–90), matters. Meanwhile the ballot families, per-ballot weights, λf, λc and the β of R1 and R2 all differ between the two collections (Table 6, l.701), and I found no selection protocol or held-out split. The evaluation uses one model, short traces (median 6 and 10 steps, l.319–320), an 80-trace subset of CORRECT-Error whose selection is not described (l.318), and only same-model voting and direct-diagnosis baselines (l.356–358). With net margins of 0 and 5 traces, these choices can decide the result. I think the idea is worth pursuing, and with cached responses and the low cost in Table 9 the missing controls should be cheap to run; my score reflects the evidence as it stands.

Questions for authors

(1) Could you add CSD's own ballot configuration, and a vote with a matched call budget, as baseline rows in Table 2, with paired tests? A significant gain of decoding over these would change my assessment.

(2) How were the per-collection configurations in Table 6 chosen? Results with one shared configuration, or with a configuration chosen on one collection and applied to the other, would address the selection concern.

(3) What happens when the conditional four-way grades are replaced by unconditional per-step grades with the same decoder and gate?

Minor (no response needed): in Table 8, the CORRECT-80 rows "Rejected, nonempty" (13→15) and "All rejected" (26→28) do not match B.3 ("from 13 to 17"), §4.3 or Table 2, since 42 + 28 = 70 rather than 72.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.