GRADE

Can one graph represent every kind of agent run? A trace records what each step did, never what it relied on, the state it read, or the results it reused. GRADE (Graph Representation of Agent Dependency and Execution) recovers that missing layer. It models any run as one typed graph over its step nodes with two edge layers:

• 🟦 Execution layer: what ran in what order, read from the trace for free (emits, handoff_to).
• 🟧 Dependency layer: what each step relied on, rarely logged, so each edge is graded by how it is known, observed, declared, or inferred (depends_on).

One representation, and each layer earns its place. This repository holds the representation, a layered structural-feature module, and the experiments that demonstrate its value: run-failure prediction across corpora, leave-one-corpus-out transfer, an observed-vs-inferred gate, off-the-shelf graph-network baselines, and step-level fault localization.

pip install -e .

Core requires Python >= 3.10 and networkx. The experiment scripts need the experiments extra; the graph-network baselines additionally need the gnn extra (PyTorch + PyTorch Geometric):

pip install -e ".[experiments]"      # numpy, scipy, scikit-learn, data loaders
pip install -e ".[experiments,gnn]"  # + torch, torch_geometric for the GNN scripts

from grade import build_graph, characterize, feature_vector

# one run = an ordered list of step dicts (idx, agent, kind, and optional deps)
steps = [
    {"idx": 0, "agent": "a", "kind": "tool_call"},
    {"idx": 1, "agent": "a", "kind": "decision", "deps": [0]},
    {"idx": 2, "agent": "a", "kind": "tool_call", "deps": [1]},
]
G = build_graph(steps, dependency="explicit", shared_resource=False)
print(characterize(G))            # node/edge/layer counts, dependency depth
names, values = feature_vector(G) # layered structural features

The figure at the top is built by this same API. Regenerate all three figures with python assets/make_figures.py (needs matplotlib).

Two demonstrated capabilities, one per layer: the dependency layer predicts failure where run size is weak, and the execution layer localizes where a run fails.

Fit on five corpora and scored on the sixth, the size-normalized dependency signal stays above chance on every held-out class. Run size, by contrast, inverts below chance on tau-bench and SWE-Gym. Dependency structure carries failure information that run size alone misses.

On Who&When multi-agent failures, ranking steps by execution-graph structure beats an early-fault position prior on top-1, top-3, and MRR, and both clear the random floor.

• build_graph(steps, *, dependency="full_context", shared_resource=True): build the typed two-layer graph. dependency is "full_context" (full-history inferred), "chain", or "explicit" (observed, from logged accesses).
• dependency_dag(G): the depends_on projection as a simple DAG.
• characterize(G): per-graph structural properties.
• downstream_reach(G, step_idx): transitive blast radius of a step.
• layered_features(G) / feature_vector(G, *, layer=...): layered structural features. layer picks the column set: "flat" (size/counts), "exec" (flat + execution topology), "full" (flat + exec + raw dependency counts). The paper's main "beyond run size" result uses "flatdep" (flat + size-normalized dependency) versus "flat"; "flatdens" is the revisit-density control and "depnorm" is the dependency-only transfer set.
• Constants: NODE_TYPES, EXECUTION_EDGES, DEPENDENCY_EDGES.

Each script prints its results to stdout (most as ROC-AUC tables). Run from the repository root:

python experiment/<script>.py

Datasets are not bundled. Most corpora download from the Hugging Face Hub at runtime (set HF_TOKEN for higher rate limits). Two need a local path:

• AgentRewardBench (the web corpus): set ARB_DIR to its data root.
• Who&When (localization): cached under experiment/.cache/whoandwhen/ (gitignored).

MIT. See LICENSE.

@misc{grade2026,
  title  = {{GRADE}: Graph Representation of {LLM} Agent Dependency and Execution},
  author = {Yue Zhao},
  year   = {2026},
  eprint = {2606.22741},
  archivePrefix = {arXiv}
}