PaperlayerView exact revision on arXiv

Source-linked AI summary

FALAT: Tracing Failures in LLM Agent Trajectories via Dependency-Guided Search

Md Nakhla Rafi, Md Ahasanuzzaman, Dong Jae Kim, Zhijie Wang, Tse-Hsun Chen

arXiv:2606.00765v1cs.AI

TL;DR

In long, interdependent LLM-agent trajectories, it is difficult to identify which agent introduced the decisive error because later steps may propagate an earlier mistake. FALAT reframes failure attribution as hierarchical dependency-guided search, using a task-conditioned prior, typed dependencies, and correction-based verification to locate decisive steps. FALAT consistently improves responsible-agent and decisive-step attribution; on algorithm-generated trajectories, it reaches 46.0 step-level accuracy versus 37.3 for CHIEF under MiniMax 2.5.

  • Problem

    In long, interdependent LLM-agent trajectories, it is difficult to identify which agent introduced the decisive error because later steps may propagate an earlier mistake.

    Source: §1 · p. 2

  • Method

    FALAT reframes failure attribution as hierarchical dependency-guided search, using a task-conditioned prior, typed dependencies, and correction-based verification to locate decisive steps.

    Source: §1 · p. 2

  • Results

    FALAT consistently improves responsible-agent and decisive-step attribution; on algorithm-generated trajectories, it reaches 46.0 step-level accuracy versus 37.3 for CHIEF under MiniMax 2.5.

    Source: §1 · p. 2

  • Takeaways & Limitations

    FALAT formulates failure attribution in LLM agent trajectories as hierarchical dependency-guided search, shifting from flat step classification to structured diagnosis over candidate steps and their dependencies.

    Source: §1 · p. 2

    FALAT relies on LLM judgments for candidate selection, transition typing, and counterfactual verification, so intermediate judgment errors may propagate through the pipeline.

    Source: §5 · p. 9

Abstract

from arXiv · show

LLM-based agents increasingly solve complex tasks through long trajectories involving reasoning steps, tool calls, and inter-agent communication. However, when these agents fail, it is often unclear which agent caused the failure and which step introduced the decisive error. This attribution problem is challenging because mistakes can propagate across the trajectory: later actions may appear incorrect, but only because they depend on an earlier corrupted state. Therefore, failure attribution cannot be treated as independent step-level classification. We propose FALAT, a diagnostic framework for failure attribution in LLM agent trajectories. FALAT frames attribution as a dependency-guided search problem. It first constructs an expectation of how the task should be solved and uses this expectation to identify suspicious regions in the trajectory. It then traces dependencies among decisions, tool outputs, and agent messages to distinguish error-introducing steps from steps that merely inherit or propagate prior mistakes. Finally, FALAT evaluates whether correcting a candidate step would be sufficient to recover the expected outcome, allowing it to identify both the responsible agent and the decisive failure step. We evaluate FALAT on the Who&When benchmark, which includes both algorithm-generated and hand-crafted multi-agent failure trajectories. The results show that FALAT consistently improves responsible-agent and decisive-step attribution. Its best configurations achieve 46.0% step-level accuracy on algorithm-generated trajectories and 29.1% on the more challenging hand-crafted trajectories, outperforming specialized attribution baselines and direct prompting with standalone LLMs. These findings suggest that dependency-aware reasoning is essential for reliable failure diagnosis in LLM agent systems.

1 Introduction

FALAT addresses the difficulty of locating decisive errors in long, interdependent agent trajectories, where downstream steps can propagate an earlier mistake. It reframes attribution as dependency-guided search and evaluates the framework on Who&When.

1 Introduction

  • Failure attribution asks which agent introduced the decisive error and when, with decisiveness defined by whether correction would recover the final outcome.Long, interdependent trajectories can make downstream steps appear reasonable while they propagate an earlier corrupted state.Source: §1 · p. 2
  • FALAT uses a task-conditioned prior and typed dependencies to prune candidate steps, then verifies whether correcting a remaining candidate would recover the expected outcome.Local verification around the predicted decisive step reduces premature commitment to plausible but non-decisive candidates.Source: §1 · p. 2
  • 46.0 step-level accuracy versus 37.3 for CHIEF under MiniMax 2.5 on algorithm-generated trajectories.On hand-crafted trajectories, FALAT reaches 29.1 step-level accuracy versus 17.0 for CHIEF under DeepSeek V3.2; it also consistently improves responsible-agent and decisive-step attribution over specialized and standalone-LLM baselines.Source: §1 · p. 2
  • The framework formulates attribution as hierarchical dependency-guided search rather than independent step classification.This structured diagnosis traces dependencies among candidate steps to distinguish error sources from downstream carriers.Source: §1 · p. 2

2 Hierarchical Dependency-Guided Search for Agent Trajectory Diagnostics

FALAT treats failure attribution as a hierarchical search for the earliest step or steps whose correction would recover the expected outcome. It uses an external task prior, typed dependencies, counterfactual checks, and local verification to distinguish error sources from downstream carriers.

2 Hierarchical Dependency-Guided Search for Agent Trajectory Diagnostics

  • FALAT searches top-down rather than classifying steps independently, using an external expectation, typed dependencies, and counterfactual sufficiency to identify decisive errors.The target is the earliest minimal set of active steps whose correction would recover the expected output; later steps may adapt to the corrected state.Source: §2 · pp. 2–3

2.1 Constructing the Search Space

  • A task-conditioned prior and aligned three-level trajectory representation guide coarse-to-fine candidate selection using relevance, prior inconsistency, and local execution inconsistency.The representation moves from execution stages to suspicious steps and raw evidence; nonoverlapping windows are processed independently to reduce positional bias.Source: §2.1 · pp. 4–5

2.2 Constructing Typed Dependencies for Candidate Pruning

  • Typed directed dependencies distinguish possible error sources from downstream carriers and prune candidates whose effects are unrelated, corrected, redundant, or unable to reach the final output.For example, follow-up links can trace a corrupted step to a downstream carrier, while correction links can remove upstream candidates whose effects no longer propagate.Source: §2.2 · pp. 5–6

2.3 Dependency-Guided Search and Verification

  • FALAT ranks candidates that introduce deviations and influence the final output, then selects the earliest candidate that introduces the error and whose correction would recover the expected output.The verification checks error independence, counterfactual sufficiency with earlier steps fixed, and temporal precedence.Source: §2.3 · pp. 6–7

2.4 Local Re-Search: Adversarial Verification

  • Local re-search compares a predicted decisive step with nearby alternatives, distinguishing root causes, propagation, symptoms, and contributing steps before confirming or replacing the prediction.The re-evaluation is designed to challenge an initially plausible choice rather than rely on it uncritically.Source: §2.4 · p. 7

3 Experiment Setup

The evaluation uses Who&When failed executions with human annotations and compares FALAT with attribution systems and direct-prompting LLM baselines. It reports agent-level accuracy, exact step-level accuracy, and step-level accuracy within tolerance windows.

Benchmark

  • Who&When contains 184 failed executions from 127 LLM-based multi-agent systems, spanning CaptainAgent-generated benchmark teams and hand-crafted Magentic-One systems.Each instance includes the full trajectory and human annotations for the responsible agent and decisive error step.Source: §3 · p. 7

Metrics

  • Evaluation measures responsible-agent accuracy, exact decisive-step accuracy, and step-level accuracy within tolerance k ∈ {1, 2, 3, 4, 5}.Exact step-level accuracy requires the predicted step to match the annotated step; tolerance accuracy accepts predictions within k steps.Source: §3 · p. 7

Baselines

  • FALAT is compared with CHIEF rerun under the same three backbones, AgentTracer-8B results from prior work, and direct-prompting LLM baselines given the full trajectory.Source: §3 · p. 7

4 Result

FALAT achieves its strongest results on both algorithm-generated and hand-crafted trajectories, with especially large gains on strict step-level attribution. Relaxed step tolerances improve localization, and ablations show that the hierarchical representation, external prior, and transition typing each contribute to performance.

Overall performance

  • 68.0 agent-level and 46.0 step-level accuracy on algorithm-generated trajectories, and 73.0 agent-level and 29.1 step-level accuracy on hand-crafted trajectories, are FALAT’s best results.Table 2 reports agent-level and exact step-level accuracy; the reported best results cover both trajectory types.Source: §4 · p. 7, Table 2 · p. 8
  • FALAT improves step-level accuracy over CHIEF by +8.7 points on algorithm-generated trajectories and +12.1 points on hand-crafted trajectories.It also improves step-level accuracy over AgentTracer by +8.7 and +5.2 points, respectively.Source: §4 · p. 8

Comparison to standalone LLMs

  • FALAT improves step-level accuracy over the strongest standalone baseline, Claude-Sonnet-4, by +7.2 points on algorithm-generated and +10.2 points on hand-crafted trajectories.Claude-Sonnet-4 scores 38.8 and 18.9 step-level accuracy on those trajectory types, respectively.Source: §4 · p. 8

Performance under tolerance windows

  • On hand-crafted trajectories, step-level accuracy rises from 22.2–29.1 at k = 0 to as high as 53.4 at ±5.The tolerance study excludes algorithm-generated trajectories because their maximum length of 10 steps would inflate relaxed-tolerance accuracy.Source: §4 · pp. 8–9, Table 3 · p. 8

Ablation study

  • Removing the hierarchical representation reduces step-level accuracy by 10.3 points on algorithm-generated and 5.0 on hand-crafted trajectories.Removing the external prior reduces algorithm-generated agent-level and step-level accuracy by 10.9 and 5.5 points, respectively; removing transition typing lowers hand-crafted agent-level accuracy by 10.5 points.Source: §4 · p. 9, Table 4 · p. 9

5 Limitations

FALAT’s effectiveness depends on reliable LLM judgments, and intermediate errors may propagate through its pipeline. Its window-based processing may miss dependencies across distant steps, while the formulation assumes failures can be localized to a small set of decisive steps.

  • FALAT relies on LLM judgments for candidate selection, transition typing, and counterfactual verification, so unreliable intermediate judgments may propagate through the pipeline.Source: §5 · p. 9
  • Window-based processing may miss long-range dependencies, and complex interactions across distant steps may remain uncaptured despite consolidation.Source: §5 · p. 9
  • The formulation assumes failures can be localized to a small set of decisive steps, which may limit attribution precision for distributed or interacting errors.Source: §5 · p. 9

6 Related Work

Prior work studies multi-agent systems and trajectory failures, but attribution remains challenging in long, interdependent executions. FALAT differs from learned attribution and causal-graph backtracking by diagnosing a single trajectory through typed dependencies and counterfactual sufficiency.

LLM-based multi-agent systems

  • Multi-agent systems use structured communication, role assignment, and tools, while automated design advances produce trajectories where errors can propagate across agents, steps, and tool outputs.FALAT focuses on diagnosing failures within a single failed trajectory.Source: §6 · p. 9

Failure attribution and trajectory analysis

  • Prior trajectory-analysis work studies loops, reasoning-action mismatches, ineffective observation use, and debugging signals, while Who&When [Zhang et al., 2025b] formalizes multi-agent failure attribution.Who&When identifies step-level localization as challenging.Source: §6 · p. 9
  • AgenTracer [Zhang et al., 2025a] learns attribution from synthetic counterfactual data, while CHIEF [Wang et al., 2026] backtracks over a reconstructed causal graph.FALAT diagnoses a single failed trajectory without task-specific training data or oracle guidance, using typed dependencies and counterfactual sufficiency.Source: §6 · p. 10

7 Conclusion

FALAT reframes failure attribution as hierarchical dependency-guided search and combines a task-conditioned prior, typed-dependency pruning, verification, and local re-search. On Who&When, it consistently outperforms existing state-of-the-art baselines across multiple LLM backbones.

  • FALAT uses a four-stage framework: task-conditioned search-space construction, typed-dependency candidate pruning, dependency-guided search and verification, and local re-search.Source: §7 · p. 10

A Prompt Templates

The prompt templates build a task-specific search space, trace typed dependencies among candidate steps, and verify likely failure sources through counterfactual checks and local re-search.

A.1 Prompts for Search-Space Construction

  • The external prior is built from the task specification, agent roster, and incorrect final output, without exposing intermediate trajectory steps.It defines expected output type, reasoning requirements, agent role boundaries, and task-specific failure risks.Source: §A.1 · p. 13
  • The hierarchical representation organizes the trajectory into high-level execution summaries, mid-level key moments, and low-level evidence for coarse-to-fine search.Prompts also analyze question requirements, agent roles, and tailored error signals while focusing on suspicious or inconsistent steps.Source: §A.1 · pp. 13–14

A.2 Prompts for Typed Dependency Construction

  • Typed dependencies label follow-ups, redundancies, unrelated steps, error shifts, corrections, and dead ends to distinguish plausible sources from carriers or prunable candidates.The prompts also trace value flow from retained candidates toward the final output.Source: §A.2 · pp. 14–15

A.3 Prompts for Dependency-Guided Search

  • Candidate verification checks shortlisted steps against localized raw evidence, typed dependencies, and linked low-level evidence.The high-confidence subset is narrowed using the external prior, dependency structure, and compressed trajectory representation.Source: §A.3 · pp. 15–16
  • Candidate selection favors steps that independently introduce errors, pass a counterfactual sufficiency check, and occur earliest among candidates meeting those criteria.The prompt returns the decisive error with supporting reasoning.Source: §A.3 · p. 16

A.4 Prompts for Local Re-Search

  • Local re-search compares the predicted decisive step with neighboring candidates through adversarial arguments, suspicion scores, role labels, and counterfactual tests.The final verdict selects the highest-suspicion candidate that passes the counterfactual test, confirming or revising the preliminary diagnosis.Source: §A.4 · pp. 16–17

B Compute and Execution Setup

Experiments use API-based inference with specified prompts, model configurations, and parameters.

B Compute and Execution Setup

  • Experiments use OpenAI API and OpenRouter access to underlying LLMs, with execution time depending on API latency and the number of calls across FALAT’s stages.No local model training or fine-tuning is required; the experiments can be reproduced by invoking the APIs with the specified settings.Source: B Compute and Execution Setup · p. 17
Loading 2606.00765v1…