Beyond Tool-Call Success: Dynamic Evidence Graphs for Runtime Effect Certification

We study runtime certification of state-changing tool use: whether an agent's claimed write effects are supported by execution-specific evidence in the realized post-state. Existing methods improve call-level consistency or select among candidate trajectories, but do not explicitly relate the grounded target, realized write, and qualified post-state witness. Consequently, apparently successful executions may modify the wrong object or produce no effect. We propose DEG, a dynamic evidence graph representation for runtime effect certification. DEG turns certification from separate checks into graph queries over explicit, dynamically maintained evidence relations: paths capture attribution and reachability, connected subgraphs support compound certificates, and evolving evidence state maintains temporal validity. Building on this representation, we certify effects over connected target–write–witness subgraphs, requiring grounded target provenance, realized-target consistency, and qualified post-state evidence attributable to the same write and valid for its post-write state. Shared graph identity further enables evidence reuse and localized maintenance across effects, while candidate selection remains decoupled from certification. Across six matched AppWorld and $\tau$-bench settings, DEG achieves 0% observed selective certificate risk (SCR), while weaker evidence tiers reach up to 28.6% SCR. The complete framework improves end-to-end execution over five baselines.