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

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.