# GRADE: Graph Representation of LLM Agent Dependency and Execution arXiv: https://arxiv.org/abs/2606.22741 · HTML: https://mlsanity.com/paper/2606.22741/ ## Key facts - Cited by 4 papers in the map (data through 14 Oct 2026). - Placed in Agent skill learning and evolution, one of 16 directions in LLM agents and tool use. - Builds on 32 of its 58 references that are in the map. - First posted on arXiv 22 Jun 2026. ## Placed in - LLM agents and tool use / [Agent skill learning and evolution](https://mlsanity.com/agents/agent-skill-learning-and-evolution/) ## Builds on (most cited first, 30 of 32) - [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022) - [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018) - [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023) - [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024) - [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017) - [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023) - [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024) - [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020) - [Designing and Interpreting Probes with Control Tasks](https://mlsanity.com/paper/1909.03368/) (2019) - [τ2-Bench: Evaluating Conversational Agents in a Dual-Control Environment](https://mlsanity.com/paper/2506.07982/) (2025) - [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025) - [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020) - [Training Software Engineering Agents and Verifiers with SWE-Gym](https://mlsanity.com/paper/2412.21139/) (2024) - [Devign: Effective Vulnerability Identification by Learning Comprehensive Program Semantics via Graph Neural Networks](https://mlsanity.com/paper/1909.03496/) (2019) - [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019) - [Learning to Represent Programs with Graphs](https://mlsanity.com/paper/1711.00740/) (2017) - [AgentRewardBench: Evaluating Automatic Evaluations of Web Agent Trajectories](https://mlsanity.com/paper/2504.08942/) (2025) - [Understanding Software Engineering Agents: A Study of Thought-Action-Result Trajectories](https://mlsanity.com/paper/2506.18824/) (2025) - [AgentOps: Enabling Observability of LLM Agents](https://mlsanity.com/paper/2411.05285/) (2024) - [AgentArmor: Enforcing Program Analysis on Agent Runtime Trace to Defend Against Prompt Injection](https://mlsanity.com/paper/2508.01249/) (2025) - [From Agent Traces to Trust: A Survey of Evidence Tracing and Execution Provenance in LLM Agents](https://mlsanity.com/paper/2606.04990/) (2026) - [GUARDIAN: Safeguarding LLM Multi-Agent Collaborations with Temporal Graph Modeling](https://mlsanity.com/paper/2505.19234/) (2025) - [From Static Templates to Dynamic Runtime Graphs: A Survey of Workflow Optimization for LLM Agents](https://mlsanity.com/paper/2603.22386/) (2026) - [DyFlow: Dynamic Workflow Framework for Agentic Reasoning](https://mlsanity.com/paper/2509.26062/) (2025) - [GNNs as Predictors of Agentic Workflow Performances](https://mlsanity.com/paper/2503.11301/) (2025) - [On Tree-Based Neural Sentence Modeling](https://mlsanity.com/paper/1808.09644/) (2018) - [CodeTracer: Towards Traceable Agent States](https://mlsanity.com/paper/2604.11641/) (2026) - [FALAT: Tracing Failures in LLM Agent Trajectories via Dependency-Guided Search](https://mlsanity.com/paper/2606.00765/) (2026) - [Topology Matters: Measuring Memory Leakage in Multi-Agent LLMs](https://mlsanity.com/paper/2512.04668/) (2025) - [Few-Shot Graph Out-of-Distribution Detection with LLMs](https://mlsanity.com/paper/2503.22097/) (2025) ## Built on by (most cited first, 4 of 4) - [TraceCompiler: Skill-Guided Mining and Compilation of LLM Agent Traces into Mostly Deterministic Workflows](https://mlsanity.com/paper/2608.02680/) (2026) - [Doomed from the Start: Early Abort of LLM Agent Episodes via a Recall-Controlled Probe Cascade](https://mlsanity.com/paper/2607.06503/) (2026) - [CatchBench: When Can an Agent Failure Be Caught?](https://mlsanity.com/paper/2608.22808/) (2026) - [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026) ## Abstract (arXiv) Traces record what LLM agents did, leaving implicit what each step relied on. GRADE holds both in one graph; six published graph views are its projections. Execution edges come free; each costly dependency edge is graded as observed in the trace, declared by added logging, or inferred under an assumption, a schema we test one grade at a time. We recover the dependency layer from six tool-use, coding, and web corpora and measure its failure-prediction gain over run size. First, over a linear run-size baseline, it improves prediction on three corpora, but the gain depends on the learner and task sampling. On held-out corpora the layer stays above chance where run size does not, under one learner, with the same task-sampling caveat. Second, structure can pass for signal it does not carry: a layer inferred under full history restates run size. Within a corpus, a preregistered test does not separate the recovered layer from a degree-matched counterfeit that rewires each step's dependencies but keeps their number. The recovered layer's largest transfer lead over it reverses when the held-out corpus's task family is withheld. Before crediting structure, grade each edge, keep a run-size baseline, and score degree-matched attachment controls.