grade - GitLite

KO | EN

gitlite — search

#anthropic #macos #dotnet #generative-ai #javascript #cloud-native #http #go #ui #ruby

grade

(★ 9)

Two-layer graph representation of LLM-agent runs (execution and dependency)

File Explorer

ZIP Download

- grade_overview.png
- localization.png
- make_figures.py
- transfer.png
- agent_failure_detection.py
- agent_failure_gating.py
- agent_failure_localization.py
- agent_graph_characterization.py
- agent_graph_openhands.py
- agent_graph_scienceworld.py
- agent_graph_swe_agent.py
- agent_graph_swebench_crossfile.py
- agent_graph_swegym.py
- agent_graph_tau2_bench.py
- agent_graph_tau_bench.py
- agent_reward_bench.py
- diagnose_layers.py
- DIAGNOSIS-layers.md
- graph_gnn.py
- graph_gnn_inferred.py
- graph_gnn_nested_ablation.py
- graph_gnn_relational.py
- size_baseline_nonlinear.py
- tau_revision_delta.py
- - __init__.py
  - features.py
- test_grade.py
.gitignore
CITATION.cff
LICENSE
pyproject.toml
README.md

# Use via CDN

jsDelivr

jsDelivr serves any public GitHub repository as a CDN with zero setup. Pick a version and a file to get a ready-to-paste link and snippet.

Version

File

Link

Example

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

<div align="center">

**A two-layer graph representation of LLM-agent runs.**

[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://raw.githubusercontent.com/yzhao062/grade/main/LICENSE)
![Python](https://img.shields.io/badge/python-3.10%2B-blue.svg)
![Status](https://img.shields.io/badge/status-arXiv%202606.22741-blue.svg)

[Install](#install) · [Quickstart](#quickstart) · [What It Finds](#what-it-finds) · [API](#public-api-grade) · [Experiments](#experiments)

</div>

<p align="center">
  <img src="assets/grade_overview.png" alt="GRADE models one run as one typed graph with an execution layer read from the trace and a source-graded dependency layer" width="92%">
</p>

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, two layers, and a separate accounting of what each one buys.
This repository holds the representation, a layered structural-feature module, and
the experiments run on it: 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.

> [!NOTE]
> Datasets are not bundled. Most corpora stream from the Hugging Face Hub at
> runtime; two need a local path. See [Data](#data).

## Install

```
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
```

## Quickstart

```python
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`).

## What It Finds

> [!IMPORTANT]
> **Revised 2026-09-08.** This section used to open: "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." The first half is withdrawn.
> It held against a linear baseline on four size counts and does not hold against a
> nonlinear one. On SWE-Gym, where the reported gain was largest, a cubic-spline fit
> on those same four counts reaches 0.832 and a chain attachment that reads no logged
> information reaches 0.827, both above the dependency model's 0.804. Read the
> transfer panel below as a description of six held-out corpora rather than as a
> capability. The execution-layer localization result is unaffected.

### Leave-One-Corpus-Out Transfer

<p align="center">
  <img src="assets/transfer.png" alt="Leave-one-corpus-out transfer ROC-AUC: size-normalized dependency clears chance on all six held-out corpora; run size drops below chance on tau-bench and SWE-Gym" width="72%">
</p>

Fit on five corpora and scored on the sixth, run size inverts below chance on
tau-bench and SWE-Gym, and adding the size-normalized dependency block lifts every
held-out corpus above chance under logistic regression. The numbers in this
paragraph are the `flatdep` panel (`flat` against `flat` plus the dependency
block); the figure above plots `depnorm`, the dependency-only set, so the two are
not the same column set. The panel reads as
compression rather than as improvement: the block lifts the weakest targets and
lowers the strongest, so the spread across the six narrows from 0.406 to 0.144,
about 2.8 times tighter, while only three of the six targets improve. The ordering
is monotone in how weak the size-only model already is on a target, which was
noticed after inspecting the results and stays exploratory. It is also specific to
this learner. The same compression is 1.383 times under gradient-boosted trees and
1.253 times under a spline, and under the spline more targets fall below chance with
the dependency block than without.

> [!WARNING]
> The plotted values in `assets/transfer.png` predate both the tau-bench upstream
> revision pin and the 2026-09-08 producer fix, so they are superseded. The comment
> at the top of `make_transfer()` in `assets/make_figures.py` says which cells moved
> and why the figure cannot be patched by hand.

### The Execution Layer Localizes the Faulting Step

<p align="center">
  <img src="assets/localization.png" alt="Step-level fault localization on Who&When: execution-graph structure beats an early-fault position prior on top-1, top-3, and MRR" width="64%">
</p>

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.

## Public API (`grade`)

- `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 primary size-plus-dependency comparison uses `"flatdep"` (flat +
  size-normalized dependency) against `"flat"`; `"flatdens"` is the revisit-density
  control and `"depnorm"` is the dependency-only transfer set.
- Constants: `NODE_TYPES`, `EXECUTION_EDGES`, `DEPENDENCY_EDGES`.

## Experiments

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

```
python experiment/<script>.py
```

| Script | Reproduces |
|---|---|
| `agent_graph_characterization.py` | representation faithfulness: every step maps to the four node types |
| `agent_graph_swebench_crossfile.py` | cross-file dependency is uncommon and shallow (SWE-bench_Verified gold patches) |
| `agent_failure_detection.py` | keystone: run-level failure prediction, run size vs run size + size-normalized dependency block |
| `agent_failure_gating.py` | the observed-vs-inferred gate and the saturation ratio that separates the regimes |
| `graph_gnn.py` | an edge-type-blind GIN trails the source-aware features |
| `graph_gnn_inferred.py` | the same GIN on observed vs inferred graphs |
| `graph_gnn_relational.py` | relation-aware GNNs (R-GCN, HGT) vs the source-aware features |
| `agent_failure_localization.py` | step-level fault localization: execution structure beats an early-fault prior |
| `diagnose_layers.py` | layer-by-layer diagnosis |

<details>
<summary>Corpus loaders and a dropped corpus</summary>

<br>

Corpus loaders build the two-layer graph per run from each trace:
`agent_graph_tau_bench.py`, `agent_graph_tau2_bench.py`, `agent_graph_swe_agent.py`,
`agent_graph_swegym.py`, `agent_graph_openhands.py`, `agent_reward_bench.py`.
`agent_graph_scienceworld.py` is a dropped corpus, kept for the record.

</details>

## Data

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).

## License

MIT. See [`LICENSE`](LICENSE).

## Citation

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