🤖 AI

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

The paper proposes FALAT, a diagnostic framework that improves failure attribution in LLM agent trajectories by framing the problem as a dependency-guided search to distinguish error-introducing steps from those merely propagating prior mistakes, thereby outperforming existing baselines in identifying responsible agents and decisive failure steps.

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

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a team of highly intelligent robots working together to solve a complex puzzle, like writing a piece of software or planning a trip. They talk to each other, use tools, and make decisions in a long chain of events. We call this chain a "trajectory."

Sometimes, the team fails. The final result is wrong. But because the chain is so long and the robots are so chatty, it's incredibly hard to figure out who made the mistake and when it happened.

Here is the problem: If Robot A makes a tiny mistake early on, Robot B might do something that looks perfectly logical based on that mistake. Then Robot C does something else that also looks logical, but is actually wrong because it's built on Robot B's error. By the time you get to the end, the whole thing is broken, but every single step seemed reasonable at the time. It's like a game of "telephone" where the message gets garbled, but everyone is convinced they heard it correctly.

The Solution: FALAT (The Detective Framework)

The authors created a tool called FALAT to act as a detective for these robot teams. Instead of just looking at the final mess and guessing, FALAT uses a clever four-step process to find the root cause.

Here is how FALAT works, using simple analogies:

1. The "Ideal Script" (Constructing the Search Space)

Before looking at the messy reality, FALAT writes down an "Ideal Script" of how the task should have gone. It knows the goal, the rules, and what a good robot should do.

Analogy: Imagine a film director who knows exactly how the movie scene should play out. When the actors mess up, the director doesn't just watch the chaos; they compare the actual filming to the script to spot where the actors went off-track.
Why it matters: If you only look at the robots' own reasoning, you might get fooled because they are all rationalizing the same mistake. FALAT uses an outside perspective (the script) to stay objective.

2. The "Zoom Lens" (Hierarchical Representation)

The robot's history might be hundreds of steps long. Reading every single word is slow and confusing. FALAT zooms out first, then zooms in.

Analogy: Think of looking at a forest. First, you look at the whole forest from a helicopter to see which area looks sick (High Level). Then you zoom in to see which group of trees is affected (Mid Level). Finally, you walk over to inspect the specific leaves on the ground (Low Level).
Why it matters: This stops FALAT from getting lost in the details. It narrows down the search to the suspicious "neighborhoods" first.

3. The "Chain of Custody" (Typed Dependencies)

This is the most important part. FALAT doesn't just blame the last person who spoke. It traces the dependencies (who relied on whom).

Analogy: Imagine a relay race where someone drops the baton.
- The Source: The runner who dropped it.
- The Propagator: The next runner who picked up the baton and kept running, even though it was broken.
- The Symptom: The runner at the finish line who crossed the line late.
- FALAT uses special labels (like "follow-up," "correction," or "dead-end") to distinguish between the person who dropped the baton and the people who just carried the broken baton. It ignores the people who were just repeating what was already said or who didn't actually affect the final result.

4. The "What-If" Test (Verification)

Once FALAT has a suspect, it doesn't just arrest them. It runs a simulation.

Analogy: The detective asks, "If we went back in time and fixed only this one step, would the whole movie turn out right?"
- If fixing Step 3 makes the final result perfect, then Step 3 is the Decisive Step.
- If fixing Step 3 still leaves the movie broken, then Step 3 wasn't the real culprit; the error happened earlier.

Does it work?

The authors tested FALAT on a benchmark called "Who & When," which contains many examples of robot teams failing.

The Result: FALAT was much better at finding the exact step where the error started compared to other methods.
The Numbers: On tricky, hand-crafted failure stories, FALAT found the right step about 29% of the time, while the next best method only got about 17%. On simpler, computer-generated stories, it got 46% right.
The Takeaway: Even though 29% sounds low, in this field of "finding a needle in a haystack," it's a huge improvement. It proves that you can't just ask a smart AI to "guess" who messed up; you need a structured way to trace the dependencies and test "what-if" scenarios.

Summary

FALAT is a diagnostic tool that stops blaming the last person in the chain. Instead, it:

Knows how things should work.
Zooms in on suspicious areas.
Traces the flow of information to separate the original error from the consequences.
Tests if fixing that one step would save the day.

It turns a messy, confusing failure into a logical investigation.

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

Problem Definition

Large Language Model (LLM) agents solve complex tasks through long trajectories comprising reasoning steps, tool calls, and inter-agent communication. When these trajectories fail, identifying the root cause is difficult due to the "attribution problem." Mistakes often propagate: an early error corrupts the execution state, causing subsequent steps to appear locally reasonable while actually inheriting the fault. Consequently, later steps may be incorrectly flagged as the source of failure.

The paper defines failure attribution as the task of identifying the specific agent ("who") and the decisive step ("when") whose correction would recover the expected final output ( $o^*$ ) from the observed incorrect output ( $\hat{o}$ ). A decisive step is defined as one where, if corrected (while allowing downstream steps to adapt), the system produces the correct outcome. Existing methods, such as single-pass LLM judges or learning-based tracers that evaluate steps independently, struggle with positional bias, order sensitivity, and the inability to distinguish between error origination and propagation.

Methodology: FALAT Framework

The authors propose FALAT, a diagnostic framework that reformulates failure attribution as a hierarchical dependency-guided search rather than independent step classification. The framework operates in four stages:

1. Constructing the Search Space

FALAT avoids relying solely on the flawed internal reasoning of the failed trajectory. Instead, it constructs:

Task-Conditioned Prior ( $\pi$ ): An external expectation of how the task should be solved, derived from the task specification, agent roles, system prompts, and available tools. This prior is independent of the trajectory's intermediate steps to prevent evaluators from being misled by the agent's own flawed logic.
Hierarchical Trajectory Representation ( $M$ ): The trajectory is abstracted into three levels to enable coarse-to-fine search:
- High Level ( $M_{hi}$ ): Global execution summaries identifying suspect stages.
- Mid Level ( $M_{mid}$ ): Local step summaries detailing agents, actions, and decisions.
- Low Level ( $M_{lo}$ ): Raw execution evidence (tool outputs, concrete values).
  This structure allows the system to first identify suspect regions and then narrow down to specific steps.

2. Constructing Typed Dependencies for Candidate Pruning

To distinguish between steps that originate an error and those that merely propagate it, FALAT constructs a directed dependency structure over candidate steps using a typed transition vocabulary. Labels include:

follow_up: Normal progression or downstream carrying of an error.
redundancy: Repetition without new evidence.
no_influence: Steps independent of the candidate's output.
error_shift: Steps introducing new deviations or transforming upstream errors.
correction: Steps that fix upstream deviations.
dead_end: Steps leading to unused outputs.

These labels allow the system to prune candidates whose effects cannot reach the final output or are merely symptoms of earlier faults, retaining only those that could plausibly be the source.

3. Dependency-Guided Search and Verification

The remaining candidates are ranked and verified against the counterfactual sufficiency objective. A candidate is considered decisive only if correcting it would recover $o^*$ . The verification process checks three criteria:

Error Independence: Does the step introduce the error, or inherit it? (Traced via backward dependency).
Counterfactual Sufficiency: Would fixing this step recover the expected outcome?
Temporal Precedence: Among valid candidates, the earliest step is selected.

4. Local Re-Search: Adversarial Verification

To mitigate "anchoring" (where an LLM judge rationalizes a plausible but incorrect candidate), FALAT performs a local re-evaluation. It extracts a bounded neighborhood around the predicted decisive step and compares the candidate against its immediate neighbors. The LLM assigns roles (ROOT_CAUSE, PROPAGATION, SYMPTOM, CONTRIBUTING) and re-ranks steps based on comparative arguments and counterfactual checks to ensure the selected step is truly decisive.

Key Contributions

Reformulation of Attribution: The paper shifts the paradigm from flat step-level classification to hierarchical dependency-guided search, explicitly modeling the distinction between error origination and propagation.
FALAT Framework: A four-stage diagnostic system that integrates an external task-conditioned prior, hierarchical abstraction, typed dependency pruning, and counterfactual verification.
Empirical Validation: Comprehensive evaluation on the Who&When benchmark (184 failed executions from algorithm-generated and hand-crafted multi-agent systems) across three different LLM backbones.

Results

FALAT was evaluated against specialized attribution baselines (CHIEF, AgentTracer) and direct prompting with standalone LLMs.

Algorithm-Generated Trajectories: FALAT achieved 46.0% step-level accuracy (vs. 37.3% for CHIEF with the same backbone) and 68.0% agent-level accuracy.
Hand-Crafted Trajectories: FALAT achieved 29.1% step-level accuracy (vs. 17.0% for CHIEF) and 73.0% agent-level accuracy.
Comparison to Standalone LLMs: Direct prompting with even large models (e.g., Claude-Sonnet-4) yielded significantly lower step-level accuracy (18.9% on hand-crafted tasks), demonstrating that model scaling alone is insufficient for reliable attribution.
Ablation Studies: Removing the hierarchical representation caused the largest performance drop (up to -10.3% step-level accuracy), followed by the removal of the external prior and transition typing.

Significance and Claims

The paper claims that dependency-aware reasoning is essential for reliable failure diagnosis in LLM agent systems. The authors argue that treating failure attribution as independent step classification fails because it ignores the causal structure of trajectories. By framing the problem as a search guided by typed dependencies and counterfactual sufficiency, FALAT effectively separates the "root cause" from "symptoms."

The findings suggest that structured search procedures provide significant benefits beyond simply increasing model scale. The framework is particularly effective at identifying the decisive step rather than just any step where an error is visible, addressing a critical gap in making autonomous agentic systems reliable and debuggable. The authors note limitations, including dependence on LLM judgment reliability and potential difficulties in capturing very long-range dependencies across window boundaries, but maintain that the proposed approach offers a robust foundation for failure attribution.