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

arXiv: https://arxiv.org/abs/2606.00765 · HTML: https://mlsanity.com/paper/2606.00765/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 33 of its 39 references that are in the map.
- First posted on arXiv 30 May 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

## Builds on (most cited first, 30 of 33)

- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023)
- [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023)
- [CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model Society](https://mlsanity.com/paper/2303.17760/) (2023)
- [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023)
- [ChatDev: Communicative Agents for Software Development](https://mlsanity.com/paper/2307.07924/) (2023)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [DeepSeek-V3.2: Pushing the Frontier of Open Large Language Models](https://mlsanity.com/paper/2512.02556/) (2025)
- [AFlow: Automating Agentic Workflow Generation](https://mlsanity.com/paper/2410.10762/) (2024)
- [Automated Design of Agentic Systems](https://mlsanity.com/paper/2408.08435/) (2024)
- [TextGrad: Automatic "Differentiation" via Text](https://mlsanity.com/paper/2406.07496/) (2024)
- [Magentic-One: A Generalist Multi-Agent System for Solving Complex Tasks](https://mlsanity.com/paper/2411.04468/) (2024)
- [Which Agent Causes Task Failures and When? On Automated Failure Attribution of LLM Multi-Agent Systems](https://mlsanity.com/paper/2505.00212/) (2025)
- [Multi-agent Architecture Search via Agentic Supernet](https://mlsanity.com/paper/2502.04180/) (2025)
- [AssistantBench: Can Web Agents Solve Realistic and Time-Consuming Tasks?](https://mlsanity.com/paper/2407.15711/) (2024)
- [Where LLM Agents Fail and How They can Learn From Failures](https://mlsanity.com/paper/2509.25370/) (2025)
- [AgenTracer: Who Is Inducing Failure in the LLM Agentic Systems?](https://mlsanity.com/paper/2509.03312/) (2025)
- [MasRouter: Learning to Route LLMs for Multi-Agent Systems](https://mlsanity.com/paper/2502.11133/) (2025)
- [Understanding Software Engineering Agents: A Study of Thought-Action-Result Trajectories](https://mlsanity.com/paper/2506.18824/) (2025)
- [EvoFlow: Evolving Diverse Agentic Workflows On The Fly](https://mlsanity.com/paper/2502.07373/) (2025)
- [TRAJECT-Bench:A Trajectory-Aware Benchmark for Evaluating Agentic Tool Use](https://mlsanity.com/paper/2510.04550/) (2025)
- [UTBoost: Rigorous Evaluation of Coding Agents on SWE-Bench](https://mlsanity.com/paper/2506.09289/) (2025)
- [Adaptive In-conversation Team Building for Language Model Agents](https://mlsanity.com/paper/2405.19425/) (2024)
- [Optimizing Model Selection for Compound AI Systems](https://mlsanity.com/paper/2502.14815/) (2025)
- [Who is Introducing the Failure? Automatically Attributing Failures of Multi-Agent Systems via Spectrum Analysis](https://mlsanity.com/paper/2509.13782/) (2025)
- [Adaptive Graph Pruning for Multi-Agent Communication](https://mlsanity.com/paper/2506.02951/) (2025)
- [Where Did It All Go Wrong? A Hierarchical Look into Multi-Agent Error Attribution](https://mlsanity.com/paper/2510.04886/) (2025)
- [GraphTracer: Graph-Guided Failure Tracing in LLM Agents for Robust Multi-Turn Deep Search](https://mlsanity.com/paper/2510.10581/) (2025)
- [From Flat Logs to Causal Graphs: Hierarchical Failure Attribution for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2602.23701/) (2026)

## Built on by (most cited first, 12 of 12)

- [How Do Agents Fail on AutoResearch: End-to-End Diagnostic Evaluation on 100 Real-World Frontier Research Tasks](https://mlsanity.com/paper/2608.14905/) (2026)
- [GRADE: Graph Representation of LLM Agent Dependency and Execution](https://mlsanity.com/paper/2606.22741/) (2026)
- [Agent Behavioral Contracts II: Certifying Compositional Reliability Without Assuming Independence](https://mlsanity.com/paper/2608.12895/) (2026)
- [SearchAuditor: Auditing and Attributing Failures in Long-Horizon Search Agents](https://mlsanity.com/paper/2608.05212/) (2026)
- [Online Monitoring and Corrective Steering of Programming Agents](https://mlsanity.com/paper/2608.06701/) (2026)
- [LongRCA Bench: Root-Cause Localization in Long-Horizon Agent Trajectories](https://mlsanity.com/paper/2608.15242/) (2026)
- [Adaptive Influence Graphs for Failure Attribution in Multi-Agent Systems](https://mlsanity.com/paper/2608.24361/) (2026)
- [Learning When and How to Intervene: A Hindsight-Distilled Sentinel for Coding Agents](https://mlsanity.com/paper/2609.39957/) (2026)
- [ReCast: Attribution-Oriented Step Representation Learning for LLM-Based Agent Systems](https://mlsanity.com/paper/2610.11334/) (2026)
- [Can Failed Trajectories Reveal Where Agents Go Wrong? Agentic Failure Attribution Without Step-Level Labels](https://mlsanity.com/paper/2610.13105/) (2026)
- [Failure Recovery via Belief Updates and World Modeling for Long-Horizon Agents](https://mlsanity.com/paper/2610.18082/) (2026)
- [BLADE: Auditing Information Use for Failure Attribution in LLM Multi-Agent Systems](https://mlsanity.com/paper/2610.18780/) (2026)

## Abstract (arXiv)

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.