Grade: Graph Representation of LLM Agent Dependency and Execution

LLM agents often fail due to 'reliance' issues—where a step consumes stale or incorrect state—yet standard execution traces only record the order of operations. This paper asks whether a unified graph representation, which explicitly models both execution flow and dependency structure, can better diagnose agent failures and provide a portable signal across different agentic frameworks.

The author introduces Grade (Graph Representation of LLM Agent Dependency and Execution), a typed graph model that represents an agent run using two distinct edge layers. The execution layer captures control flow (read for free from traces), while the dependency layer captures state reliance (observed, declared, or inferred). A key innovation is the 'attachment grade,' which labels each dependency edge by its source, allowing the model to distinguish between hard-observed dependencies and weaker, inferred assumptions. The author evaluates this representation across six corpora covering tool use, software engineering, and web navigation.

• Failure Prediction: The dependency layer provides significant predictive lift in scenarios where run size is a weak indicator of failure. In size-weak corpora, adding dependency structure improves ROC-AUC scores, whereas in size-strong corpora, it remains neutral.
• Transferability: Unlike run-size metrics, which can invert (predicting failure in the wrong direction) when transferred across different agent classes, the dependency structure provides a consistent, portable signal that stays above chance across all tested corpora.
• Fault Localization: The execution layer effectively localizes the specific step where a multi-agent run fails, complementing the dependency layer's ability to identify the root cause of reliance-based failures.
• Model Limitations: The paper demonstrates that generic graph neural networks often fail to capture this signal because they lack a mechanism to distinguish between measured dependencies and those that are merely artifacts of run length.