Technical Summary: Leveraging Trajectory Graphs for Pre-Execution Error Diagnosis in Agentic LLM Systems

Problem Statement

Large Language Model (LLM) agents have demonstrated proficiency in complex interactive tasks, particularly in domains like embodied AI. However, these agents frequently struggle with long-horizon tasks due to compounding errors. In such settings, a single suboptimal action can derail an entire trajectory, causing the agent to exhaust its limited step budget on inefficient or unrecoverable paths.

Existing strategies to mitigate this often rely on post-hoc learning (e.g., environmental exploration or refinement learning). These approaches share a fundamental limitation: they learn primarily from the final outcomes of entire trajectories. Consequently, they struggle to pinpoint the specific, step-level actions that lead to failure. Without granular, causal feedback explaining why a specific action was incorrect (e.g., targeting a non-existent object), agents learn inefficiently from sparse signals and are prone to repeating similar mistakes.

Methodology: Trajectory Graph Copilot

To address these limitations, the authors propose Trajectory Graph Copilot, a framework that shifts the paradigm from post-hoc analysis to proactive, step-level error diagnosis. Drawing inspiration from software debugging, the system acts as a "copilot" that analyzes intended actions before execution to flag potential errors.

The core component of this framework is the Graph Debugger, which operates through the following stages:

1. Graph Construction (PGM-based)

The method models the agent's interaction as a Partially Observable Markov Decision Process (POMDP). Instead of treating trajectories as simple text sequences, the framework transforms historical trajectories into a probabilistic graph:

• Nodes: Represent actions ($A$).
• Edges: Encode observations ($O$) linking consecutive actions.
• Representation: This forms an action-centric heterogeneous graph ($G = (V, E)$) where $V \subseteq A$ and $E \subseteq O$. This structure captures the underlying dependencies between actions and observations, effectively adapting the classical state-transition diagram to handle partial observability by treating observations as edge attributes.

2. Potential Error Diagnosis

The error diagnosis task is formulated as a node classification problem on the constructed graph.

• Embedding: Pre-trained BERT models initialize embeddings for actions and observations.
• Detection Mechanism: A Graph Neural Network (GNN), specifically adapted from TextGCN, is employed. The GNN performs $K$ rounds of message passing to aggregate information from neighboring nodes.
• Output: The model outputs a probability distribution over a set of fine-grained error categories (e.g., Precondition Not Met, Illegal Action, Repeated Action, Condition Met but Action Not Taken).
• Theoretical Advantage: The authors argue that graph-based methods possess a lower Bayes risk and sample complexity compared to sequence-based methods (like standard text classification or retrieval) because the graph representation acts as a sufficient statistic (Markov blanket) for the error label, capturing structural dependencies more efficiently.

3. In-Context Learning (ICL) Feedback

Rather than fine-tuning the underlying LLM, the framework integrates the diagnostic signals into the agent's reasoning loop via In-Context Learning.

• When the Graph Debugger identifies a potential error in a proposed action, it generates a feedback signal (error type and explanation).
• This feedback is appended to the agent's prompt, conditioning the model to regenerate the action based on the revised distribution: $P(A'_{i+1} | \text{History}, \text{Proposed Action}, \text{Feedback})$.
• This allows the agent to self-correct in real-time without modifying its parameters.

Key Contributions

1. Graph Debugger: A novel method based on a probabilistic graph model designed specifically for step-level action error detection in LLM agents.
2. Trajectory Graph Copilot Framework: An integration of the detection module as a distinct, external "diagnostic sandbox" that provides real-time error warnings, enhancing agent performance without costly fine-tuning.
3. Empirical Validation: Extensive experiments demonstrating the superiority of the graph-based approach over traditional text classification, retrieval-based methods, and LLM-as-a-judge baselines.

Experimental Results

The framework was evaluated on four benchmarks: AlfWorld, TextWorld, ScienceWorld, and TravelPlanner, using three different LLM agents (GPT-4o-mini, Qwen2.5, and Gemma3).

• Error Detection Performance: The Graph Debugger consistently outperformed baselines. On average, it achieved a >5% improvement in accuracy over text classification methods. The advantage was most pronounced in AlfWorld, where it outperformed the second-best approach by 10.23%.
• Task Completion (Pass Ratio): When used as a feedback mechanism, the framework improved the agents' pass ratio by an average of 14.69% across all benchmarks and agents.
• Comparison with Prompting Strategies: The method outperformed established prompting-based agents like ReAct and Reflexion, which rely heavily on the inherent reasoning capabilities of the LLM and often suffer from error accumulation.
• Sample Efficiency: Theoretical analysis and empirical results suggest that the graph-based approach requires fewer samples to achieve the same error detection rate compared to sequence-based methods.

Significance and Claims

The paper claims that Trajectory Graph Copilot offers a significant advancement in making LLM agents more reliable for long-horizon tasks. By mimicking the software debugging process—analyzing execution logs to preemptively catch errors—the system prevents the accumulation of costly mistakes that would otherwise doom a task.

Key claims regarding significance include:

• Proactive vs. Reactive: Unlike post-hoc learning, this method prevents errors before they are executed, preserving the agent's step budget.
• Generalization: By acting as a diagnostic sandbox rather than a fine-tuned model, the approach minimizes bias introduced by fixed datasets, leading to better generalization on new tasks.
• Efficiency: The graph-based representation captures sequential dependencies more effectively than raw text sequences, offering higher performance with lower data complexity.

The authors conclude that this work provides a general framework for improving decision-making in LLM agents, suggesting that integrating structured, graph-based diagnostic modules can be a viable path toward more robust and reliable AI systems.