Who is Introducing the Failure? Automatically Attributing Failures of Multi-Agent Systems via Spectrum Analysis

Context

• Failure attribution remains difficult because MAS logs combine complex agent, tool, and reasoning interactions with ambiguous natural-language descriptions of actions and resulting states.Accurately identifying the action that produced the state directly leading to failure is needed for root-cause debugging and system improvement.Source: §1 · p. 1

State of the art and approach

• Existing benchmarks leave attribution to manual analysis, while LLM-based approaches have achieved limited success, including less than 10% action-level accuracy for Zhang et al..FAMAS applies spectrum-based analysis to repeated executions, assigning higher scores to actions that recur more often across counterpart trajectories.Source: §1 · p. 2

Results

• 29.35% action-level attribution accuracy was achieved by FAMAS on Who&When, 49.13% higher than Zhang et al..The benchmark contains 184 failure traces from 127 MASs, and FAMAS also achieved top performance overall.Source: §1 · p. 2

2.1 Large Language Model Powered Multi-Agent Systems

• A turn-based MAS is modeled with agents, system states, agent-specific actions, state transitions, and a schedule selecting the active agent at each step.An execution trajectory records successive actions and resulting states, and a binary function indicates whether the query succeeds.Source: §2.1 · pp. 2–3

2.2 Failure Attribution in MAS

• Failure attribution identifies the decisive action and state in a failed trajectory, where subsequent actions from the error-decisive state diverge from normal execution and lead to failure.The target is the specific agent–action–state tuple that constitutes the decisive error.Source: §2.2 · pp. 3–4

2.3 Spectrum-Based Fault Localization

• Spectrum-based fault localization uses execution outcomes and component coverage to calculate suspiciousness scores and rank potentially faulty components.Representative formulas include Ochiai, Tarantula, Jaccard, Dstar2, and Kulczynski2.Source: §2.3 · p. 4

Attribution challenges

• Manual attribution is time-consuming and expertise-intensive, while LLM judging can be distracted by noisy log entries and superficially salient error text.For handcrafted MASs, Zhang et al. achieved 7.02% action-level accuracy, compared with a 4.16% random baseline.Source: §3 · pp. 4–5

Spectrum-analysis motivation

• Repeated executions provide trajectories in which recurring actions and resulting states can be analyzed to attribute a failed run.The motivating example contrasts a recurring erroneous web search in failed runs with a more effective alternative in successful runs.Source: §3 · p. 5

Trajectory characterization

• FAMAS converts lengthy logs into structured agent–action–state triples using chunked LLM analysis and hierarchical clustering to reconcile semantic variations.The clustering first identifies agents and then groups action–state pairs, producing consistent trajectories for spectrum analysis.Source: §3 · p. 6

Agent Behavior Group

• The Agent Behavior Group uses coverage ratio and frequency proportion to account for differences in agent activation and normalize action frequency within each agent.These metrics are intended to avoid frequency comparisons that favor more active agents.Source: §3 · p. 6

Action Behavior Group

• The Action Behavior Group combines a local frequency enhancement factor for repeated actions with a λ-decay coefficient that attenuates globally recurring repetitions.This design distinguishes unusually frequent actions in failing trajectories from recurrent meta-actions that appear in both successful and failing runs.Source: §3 · p. 6

Trajectory Replay & Abstraction

• FAMAS re-executes the failed task multiple times to collect raw logs and uses LLM-based hierarchical clustering to structure them as execution trajectories.The abstraction step is intended to mitigate natural-language ambiguity before spectrum analysis.Source: §4 · p. 7

Spectrum Analysis

• Spectrum analysis estimates scores for actions using a suspiciousness formula that evaluates behavior at both agent and action levels.The analysis operates over the structured trajectories collected from repeated executions.Source: §4 · p. 7

Attribution result

• FAMAS ranks entities in the original failed trajectory by their spectrum scores and returns the top-ranked entity as its attribution.Source: §4 · p. 7

4.1 Phase 1: Trajectory Replay & Abstraction

• The phase acquires logs from multiple MAS runs and transforms them into structured trajectories through replay and abstraction, followed by clustering and refinement.The runs yield execution logs that may succeed or fail because of nondeterministic agent interactions.Source: §4.1 · p. 7, Step 1.1: Primitive Trajectory Replay… · p. 7

Step 1.1: Primitive Trajectory Replay & Abstraction

• An LLM parses manageable chunks of each heterogeneous log into canonical agent–action–state triples, representing the acting agent, its behavior, and the resulting state.The resulting structured trajectories make the raw logs suitable for analysis.Source: Step 1.1: Primitive Trajectory Replay… · p. 7

Step 1.2: Hierarchical Clustering & Trajectory Refinement.

• Clustering first groups primitive triples by agent, then groups action–state descriptions by semantic similarity to produce consistent abstractions.Each primitive trajectory is refined by replacing its triples with corresponding cluster representatives, consolidating semantically equivalent behaviors.Source: Step 1.2: Hierarchical Clustering &… · p. 8, Trajectory Output · p. 8

Trajectory Output.

• FAMAS ranks agent–action–state triples by suspiciousness and uses the highest-ranked triple as its final fault-attribution output.The abstracted trajectories are refined into representative triples that capture essential MAS behavior.Source: Trajectory Output · p. 8

4.2 Phase 2: Spectrum Analysis in MAS

• The spectrum-analysis formula combines Action Coverage Ratio (γ), Action Frequency Proportion (β), Global Frequency Decay, and Local Frequency Enhancement (α) in two behavior groups.The Agent Behavior Group contains γ and β; the Action Behavior Group contains λ-decay and α.Source: §4.2 · p. 8

4.2.1 Matrices for Spectrum Analysis

• Coverage and frequency matrices record triple presence and occurrence counts by trajectory, while an outcome vector marks each execution as successful or failed.Analogous agent-level matrices support analysis of agent behavior alongside triple-level patterns.Source: §4.2.1 · pp. 8–9

4.2.2 Agent Behavior Group

• Action Coverage Ratio (γ) measures how broadly an action–state pair appears across an agent’s executions, while Action Frequency Proportion (β) measures its relative importance in that agent’s behavior.Together, they represent contextual breadth and behavioral intensity to address differing agent activity levels.Source: §4.2.2 · p. 9

4.2.3 Action Behavior Group.

• The λ-decay coefficient captures cross-trajectory frequency patterns, while Local Frequency Enhancement (α) emphasizes abnormal repetition within a failing trajectory.The decay factor attenuates redundant repetitions while preserving initial occurrence signals; the paired metrics target global patterns and locally concentrated anomalies.Source: §4.2.3 · pp. 9–10

4.2.4 Suspiciousness Calculation and Ranking

• The final output is the top-ranked agent–action–state triple, selected by descending suspiciousness scores that combine failure correlation with behavioral anomalies.The score integrates the two behavior groups using Kulczynski2 as its base spectrum-based fault-localization formula.Source: §4.2.4 · p. 10

5.1 Evaluation Setup

• The evaluation uses Who&When’s 184 annotated failure logs from 127 MASs and compares Famas with 12 approaches using strict top-1 agent- and action-level accuracy.The benchmark logs were annotated by three experts; Famas uses Qwen2.5-72B for trajectory replay and abstraction, with k=20 and λ=0.9 by default.Source: §5.1 · pp. 10–11

5.3 RQ2: Comparison against Baselines

• On the Who&When benchmark, Famas outperforms all 12 baseline methods, attaining the highest failure-attribution accuracy: 57.61% at the agent level and 29.35% at the action level.Source: §5.3 · p. 12

5.2 RQ1: Effectiveness and Efficiency of Famas

• On 184 failure logs, Famas attributes 106 cases at the agent level and 54 at the action level, with average task time of about 105 minutes.Spectrum analysis typically takes under a minute; replay and abstraction are the primary computational bottleneck. Accuracy is higher on 58 handcrafted logs than on 126 algorithm-generated logs, particularly at the action level.Source: §5.2 · pp. 11–12

5.4 RQ3: Configurations of Famas

• Correct attributions rise with replay quantity: agent-level averages increase from 99.6 at k=5 to 104.6 at k=15, and action-level averages from 46.0 to 50.8.The study reports five repetitions per configuration; the authors note that trajectory quantity and representativeness affect effectiveness.Source: §5.4 · p. 14, Figure 4 · p. 14
• Successful attributions peak around λ=0.90–0.95; at λ=1.00 they fall to 103 agent-level and 46 action-level cases.As λ increases from 0.65 to 0.95, agent-level attributions rise from 104 to 106 and action-level attributions from 47 to 54.Source: §5.4 · p. 14, Figure 5 · p. 14
• Famas improves over the base formula from 100 to 106 agent-level and from 39 to 54 action-level successes; removing any component reduces performance, with λ removal causing the largest decline.The ablation varies decay λ, action coverage γ, and action frequency proportion β.Source: §5.4 · pp. 14–15, Table 3 · p. 14

6.1 Impact of Log Complexity on Failure Attribution Performance

• FAMAS performs better on handcrafted than algorithm-generated logs, especially at the action level, where algorithm-generated logs are limited to 10 steps.Handcrafted logs are grouped into five complexity levels by step count, from 0–11 steps at Level 1 to 52–65 at Level 5.Source: §6.1 · p. 15
• Accuracy peaks at complexity Levels 2–3 and declines at Levels 1 and 4–5, where limited context or difficulty isolating decisive steps poses challenges.Figure 6 presents agent- and action-level accuracy across five step-count levels.Source: Figure 6 · p. 15, §6.1 · p. 15
• Hierarchical context modeling and selective trajectory pruning are proposed as future directions for improving performance across log complexities.Source: §6.1 · p. 15

6.2 Threads to Validity

• The authors identify implementation correctness as an internal-validity threat and subject selection as an external-validity threat, using Who&When to mitigate the latter.They describe Who&When as providing diverse failed trajectories across MAS types and realistic scenarios.Source: §6.2 · p. 15
• Construct validity depends on the selected agent- and action-level accuracy metrics and FAMAS parameters; the authors examine both in their evaluation.The metrics are described as widely used in related work [43], and parameter settings and impacts are addressed in Sections 5.1 and 5.4.Source: §6.2 · p. 16

Failure Analysis in MASs

• Earlier MAS failure work includes taxonomies from MAST and TRAIL [3], an interactive debugging tool from AGDebugger [4], LLM-as-a-judge attribution from Zhang et al., and fine-tuned attribution from AgentTracer [43].FAMAS distinguishes itself by applying spectrum analysis rather than directly using LLMs for attribution.Source: §7 · p. 16

Testing of MASs

• MAS testing benchmarks and red-teaming address system effectiveness and vulnerabilities, but failure attribution remains largely unexplored.The cited benchmarks include AgentBench [19], SWE-Bench, and GAIA [24]; red-teaming includes jailbreaking [31] and prompt injection [20] [32].Source: §7 · p. 16

Fault Localization in Traditional Software

• Traditional software fault localization includes spectrum-, mutation-, program-slicing-, and learning-based techniques; SBFL is widely studied for its lightweight scalability, which FAMAS extends to MASs.The cited technique families are spectrum-based [2], mutation-based, program-slicing-based [33], and learning-based [17].Source: §7 · p. 16

• FAMAS achieves the best performance compared with 12 baselines on the Who&When benchmark.Source: §8 · p. 16
• FAMAS identifies the root cause of a failed trajectory by applying spectrum analysis to multiple trajectories collected through repeated task execution.Source: §8 · p. 16
• Its novel suspiciousness formula captures both agent activation and action activation patterns in execution trajectories.Source: §8 · p. 16