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

In plain words

When a team of AI agents fails at a task, the hard question is which agent made the mistake that doomed the run, and at which moment. A wrong step often looks wrong only because it built on an earlier bad step. Reading the log from top to bottom and asking "is this step wrong?" tends to blame the symptoms.

The approach here works more like a detective's search. First it writes down what a correct run should look like, using only the task and the team setup, not the failed run itself. It then cuts the long log into chunks and zooms in on the suspicious ones. Next it asks, for each suspect, whether the step caused the problem or just passed on a problem it received. Finally it asks the decisive test question: if this one step were fixed, would the final answer come out right? Suspects that pass get a closer look from their neighbours before a verdict is given.

This matters because operators of agent systems need the responsible agent and the exact step to debug, not only a sense that something went wrong.

TL;DR

• FALAT (named as "TrajFL" in some source files) attributes a failed multi-agent run to a responsible agent and a decisive step §1 §2.
• It is a search, not a single judge: a task-only prior, a window abstraction, typed dependencies, a counterfactual check and a local re-search §2.
• Evaluated on Who&When (184 failed runs), the paper reports higher agent-level and step-level accuracy than CHIEF, AgenTracer-8B and direct prompting tab. 2.
• All numbers are author-reported. Several steps depend on LLM judgments, and the window size and sampling settings are not stated §5 §3.

Problem

Failure attribution asks which agent introduced the decisive error and at which step §1. Errors propagate: a later step can look incorrect only because it depends on an earlier corrupted state §1. The authors argue that step-by-step classification ignores this dependency structure §1 §2.

The paper names three weaknesses of prior approaches §1: single-pass LLM judges are sensitive to position and to the order of evidence, and they revise hypotheses poorly across long chains; learning-based tracers that score candidate steps independently generalise poorly. The method is built on the assumption that a failure can be localised to a small set of decisive steps under a counterfactual correction §5. The paper states that this assumption may not hold when errors are distributed or interact §5.

The formal target is a minimal set of active steps whose correction, with later steps allowed to adapt, makes the final output equal to the expected output §2. In the single-step case, the decisive index is the minimum of that set §2.

Method

FALAT runs four stages §2 fig. 1. The paper's design principles are expectation-guided search, separation of error sources from propagation, and counterfactual sufficiency §2.

Notation §2: a trajectory is a sequence of T steps, each step with reasoning, an action or message, and an output. A step counts as active when it makes a decision of its own, such as looking something up, calculating, filtering, calling a tool or running code; it counts as passive when it merely forwards earlier information §2. The paper defines the decisive step set as a minimal set of active steps whose counterfactual replacement yields the expected output; the formula is unnumbered §2.

Stage 1: search space (§2.1)

1. Build a task-conditioned prior π from the task specification Q, the agent set, the agents' roles and system prompts, the available tools, and the wrong final output ô. The prior is built without the trajectory's intermediate steps §2.1 app. A.
2. Split the trajectory into consecutive, non-overlapping windows of k steps (the last window may be shorter), so that there are N = ceil(T/k) windows. The value of k is not stated §2.1.
3. For each window, keep the raw steps as the low level, summarise them into a mid level of step summaries (index, agent, action, decision, significance), and abstract them into a high level of stage summaries. Both summaries are conditioned on π §2.1 tab. 1.
4. Build the error candidate set C. A step enters C if an aligned view shows at least one of three signals: outcome relevance (the step belongs to a stage or transition that contributes to the outcome), prior inconsistency (the action, decision or transition conflicts with π), or local execution inconsistency (the stated reasoning, executed action and observed output disagree) §2.1.
5. Merge adjacent candidate indices into contiguous regions so that candidates that span a window boundary are kept together §2.1.

Stage 2: typed dependencies (§2.2)

1. For each ordered pair of candidate steps i < j, assign one of six transition labels: follow_up, redundancy, no_influence, error_shift, correction, dead_end §2.2 app. A.
2. follow_up from a corrupted step marks a downstream carrier, and attribution is traced back to the source §2.2.
3. Prune candidates whose effects are redundant, corrected, unrelated to the output, or dead ends, unless they deviate from π on their own §2.2.
4. Keep candidates connected by error_shift as possible error sources. The result is a refined set C' that is a subset of C §2.2.

The labels are assigned by the LLM, not by a deterministic rule §2.2 app. A.

Stage 3: dependency-guided search and verification (§2.3)

1. Rank the refined set using three signals: the step makes an incorrect execution decision (wrong tool, flawed code, misused data); it introduces or relies on unverified or fabricated information relative to π; it lies on a typed transition path that affects later reasoning or the output §2.3.
2. Retain three top-ranked candidates as the high-confidence set C_H in the experiments, or every remaining candidate when fewer than three survive §2.3.
3. For each candidate in C_H, build a local verification context: π, the raw steps i-1, i, i+1, the transitions that involve i, and linked low-level evidence. Raw code and full tool outputs replace summaries where available §2.3 app. A.
4. Judge each candidate on three criteria §2.3: error independence (does it introduce the error, or inherit it via error_shift versus follow_up), counterfactual sufficiency (would correcting its output, decision or assumption recover the expected output while earlier steps stay fixed and later steps adapt), and temporal precedence (among those that pass, take the earliest).
5. The candidate that passes all three is the predicted decisive step t_hat, with agent a_hat §2.3.

Stage 4: local re-search (§2.4)

1. Take the bounded neighbourhood of t_hat: steps max(1, t_hat-2) to min(t_hat+2, T) §2.4 app. A.
2. Pass the LLM the prior, the transitions that matter and the full representation. For every step in the window it weighs arguments for and against being decisive, then assigns one role: ROOT_CAUSE (independently introduces the decisive error), PROPAGATION (carries an upstream error forward), SYMPTOM (reflects an error without materially affecting downstream computation), or CONTRIBUTING (is wrong but not sufficient alone) §2.4 app. A.
3. Rank the window steps from most to least likely decisive, using the roles, the arguments, the transitions and a counterfactual check §2.4.
4. Confirm t_hat if it is still ranked first, or replace it with a higher-ranked neighbour. The output is the verified step t_tilde and agent a_tilde §2.4 app. A.

# FALAT pipeline  [§2] [fig. 1]
# Input:  task Q, agents, prompts, tools, wrong output o_hat,
#         trajectory tau of T steps (reasoning, action, output)
# Output: verified decisive step t_tilde and its agent a_tilde

def attribute_failure(Q, agents, prompts, tools, o_hat, tau):
    # Build the expected-behaviour prior from the task only  [§2.1] [app. A]
    prior = build_prior(Q, agents, prompts, tools, o_hat)

    # Cut tau into windows of window_size steps; size not stated  [§2.1]
    windows = split_into_windows(tau, window_size)

    # Three aligned levels per window: raw, step, stage  [§2.1] [tab. 1]
    memory = [build_levels(w, prior) for w in windows]

    # Keep steps with an outcome, prior or execution signal  [§2.1]
    # Then merge adjacent candidate indices into regions  [§2.1]
    candidates = select_candidates(memory, prior)
    candidates = merge_adjacent(candidates)

    # Label every pair i < j with one of six transition types  [§2.2] [app. A]
    transitions = label_transitions(candidates, memory)

    # Drop candidates whose effects cannot reach the output  [§2.2]
    refined = prune_candidates(candidates, transitions)

    # Keep the top_k = 3 candidates by deviation and propagation  [§2.3]
    high_confidence = rank_top_k(refined, prior, transitions, top_k=3)

    # Check error independence and counterfactual sufficiency  [§2.3]
    verdicts = [verify(c, prior, transitions, tau) for c in high_confidence]

    # Choose the earliest candidate that passes both checks  [§2.3]
    t_hat, a_hat = earliest_passing(verdicts)

    # Compare t_hat with neighbours in [t_hat - 2, t_hat + 2]  [§2.4]
    t_tilde, a_tilde = local_research(t_hat, tau, prior, transitions)
    return t_tilde, a_tilde

Metrics are defined in §3. Agent-level accuracy checks the responsible agent. Step-level accuracy checks the exact decisive step. Tolerance accuracy counts a prediction as correct if |t_hat - t*| is at most k, for k from 1 to 5.

Hyperparameters

The paper states no learned parameters, because the pipeline is prompt-driven app. B.

Results

Author-reported. Setup: Who&When §3, 126 algorithm-generated and 58 hand-crafted failed runs tab. 2. Baselines: CHIEF re-run by the authors on the same three backbones; AgenTracer-8B and the direct-prompting rows adopted from the AgenTracer paper §3. Hardware is not stated.

Agent and Step columns are accuracy in percent tab. 2. Bold marks the best value in each block, as in the source.

Headline numbers §1 §4: 46.0 step-level on algorithm-generated runs (MiniMax 2.5) and 29.1 on hand-crafted runs (DeepSeek V3.2). The paper reports the agent-level best as 68.0 (MiniMax 2.5) on algorithm-generated runs and 73.0 (DeepSeek V3.2) on hand-crafted runs §4 tab. 2.

Tolerance results, hand-crafted runs only §4 tab. 3. Algorithm-generated runs are excluded because they have at most 10 steps, which would inflate tolerance scores §4.

Ablation, GPT-5.4-Mini backbone only §4 tab. 4. Values in parentheses are the ablated value minus the full value.

Stage structure is shown in the overview figure, which is cited as fig. 1. The paper describes the candidate hierarchy in tab. 1. Its three rows are the high level (stage summaries that point to suspect regions), the mid level (step summaries that localise suspicious steps), and the low level (raw evidence used for verification) tab. 1.

Paper vs code

No official code.

Search performed on the release date of this card: (1) the paper's links, abstract and arXiv metadata contain no code link; the paper's text has no release URL in the published version (a commented-out line in the LaTeX source has an unfilled placeholder, which was not used); (2) no project page is linked; (3) GitHub repository search for "FALAT" returned no matching repositories, "FALAT agent failure" returned none, and "TrajFL" returned only unrelated trajectory-prediction repositories. The authors are at the SPEAR Lab, Concordia University, and no lab or organisation GitHub account was linked from the paper.

No code was cloned, so the pitfalls below rely on the paper text and on the prompts in app. A only.

Pitfalls

• Headline numbers mix backbones. The 46.0 and 29.1 step-level figures come from different backbones (MiniMax 2.5 and DeepSeek V3.2) tab. 2. Compare like with like by reading the same-backbone rows.
• Cross-backbone gain in the text. The paper's claim of +12.1 step-level points over CHIEF on hand-crafted runs subtracts CHIEF under MiniMax 2.5 (17.0) from FALAT under DeepSeek V3.2 (29.1) §4 tab. 2. Under the same DeepSeek backbone, CHIEF scores 10.3, a gain of 18.8 points.
• Window size is missing. The paper gives no value for k, the number of steps per window §2.1. Results depend on it, and the published text does not say how it was chosen. Choose one, record it, and test sensitivity.
• Sampling settings are missing. Temperature, seeds, repeats and token budgets are not stated in the published text §3. The LaTeX source contains a commented-out passage with such settings from an earlier draft; it is not part of the paper and this card does not use it.
• Ranking function is qualitative. The three ranking signals and the suspicion scale in app. A are described in words; no scoring formula or weights are given §2.3. The verification prompt asks for a JSON object, but parsing and retry rules are not stated app. A.
• Counterfactual test is an LLM judgement. Counterfactual sufficiency is decided by asking the model whether correcting a step would recover the expected output. No replay or execution of the corrected run is described §2.3 §5. Treat it as a model judgement, not a measured effect.
• Expected output is an input. The method needs the expected output o* to judge counterfactual sufficiency §2.3. The prior is built from the task, agents, prompts, tools and the wrong answer §2.1. How the expected output is obtained in practice is not described in the published text.
• Ablation is on one backbone. The ablation table uses GPT-5.4-Mini only tab. 4. The headline backbone (MiniMax 2.5) is not ablated.
• External prior is not uniformly helpful. The ablation text calls the external prior critical §4. On hand-crafted step accuracy, removing it gives 22.4 versus 22.2 for the full method (+0.2) tab. 4.
• Baseline numbers are adopted. AgenTracer-8B and direct-prompting numbers are copied from the AgenTracer paper, not re-run §3. Check that paper's evaluation setting before comparing these rows with other runs.
• Localised-failure assumption. Failures spread across several steps, or interacting errors, may fall outside the model §5. The tolerance table shows that exact step accuracy is modest even though near-misses are common tab. 3.
• Window boundaries. Windows are processed independently, so long-range dependencies across windows may be missed; consolidation is only partial §2.1 §5.
• Cost. A single diagnosis issues several LLM calls per stage: abstraction for every window, pairwise typing, verification per candidate, and local re-search. The paper does not report call counts or cost app. B.

Lineage

• Builds on: classical abstraction hierarchies in planning and temporal abstraction in reinforcement learning, cited as the basis for the coarse-to-fine search §2.1. Uses the Who&When formal definition of the decisive step §2.
• Compared against: Who&When, the benchmark and step-level definition from ICML 2025 (no arXiv id in the source) §3; CHIEF, arXiv:2602.23701, re-run by the authors §3; AgenTracer-8B, arXiv:2509.03312, results adopted from its paper §3.
• Related card on the same problem: Causal Agent Replay, which also evaluates on Who&When.
• Superseded by: not stated.