acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Effect certification, tool-use, dynamic graph

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_2jHAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

DEG checks whether an agent's claimed write actually happened to the intended target. It connects the target, write and post-state evidence, then tracks when that evidence becomes stale. Across six settings, it reports no observed false certificates and better task completion with the full system. However, the paper suffers several wekaness. The case for the graph representation is weaker than the case for tracking these evidence relations. Another weakness is that the end-to-end comparison does not cleanly isolate certification.

Critical strengths
  1. IMHO, the distinction between a successful tool call and a verified effect is useful. The attribution, reachability, stale-evidence interventions make the failure modes concrete. I also appreciate the explicit limit that certifying a write does not certify the whole task.

  2. The paper goes beyond its own checker with an execution audit. It also reports uncertainty around zero observed errors. That matters here, since the two AppWorld settings produce only four and seven certificates. Zero observed errors alone would be easy to overread.

Critical weaknesses
  1. The case for the graph representation is weaker than the case for tracking these evidence relations. Appendix B.3's EffectRecord baseline gives the same certificates and outcomes. Although the graph's remaining advantage is efficiency, I would want a comparison with a record implementation that also memoizes checks and invalidates only affected evidence. Otherwise, some savings may come from avoiding redundant calls rather than from the graph itself.

  2. Another weakness is that the end-to-end comparison does not cleanly isolate certification. Appendix B.1 gives full DEG a native candidate pool plus graph-guided execution, while the candidate-pool oracle only selects from that pool. This makes the completion gains hard to attribute. For Gemini, Table 8 also shows a small difference between the selector and full DEG: 153 versus 154 passed sub-tests out of 262.

Questions for authors
  1. Clarification: what are the total candidate-generation, inference as well as tool budgets for full DEG versus the strongest selector? Does the gain remain when those budgets match?

  2. Additional evidence: how much of the graph's efficiency gain remains against a memoized, scope-aware EffectRecord baseline? This would help establish the representation's contribution.

Reviewer_SbooOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper try to address a very practical issue where a successful tool call does not necessarily mean the desired effect is applied. The authors showed that independent checks and post-state observations are insufficient, and proposed the DEG framework. DEG maintains a small dynamic graph with evidence nodes (reads, post-write read-backs) and effect nodes (writes). Object-flow edges record target provenance, combining with verification edges that attach a post-write "witness" to a specific write and scope/version metadata that decide when evidence becomes stale. A write is admitted for commit only if every bound target has a complete, fresh provenance path, and the commit certificate additionally requires write, witness and effect checks pass. Importantly, the evidence is shared across effects, so the certification can actually prove the whole tool call sequences yield the desired effects.

Overall, the paper's main contribution is a systems-style integration and the detailed analysis. The findings provides useful insights on how to design similar systems. I found Findings 2 and 10 the most informative results in the paper. Finding 2 shows that the certificates gained by relaxing the acceptance rule are almost all false (29/29 for PL, 32/39 for DEG). This suggests coverage should come from more evidence, not lower thresholds. Finding 10 shows that all 123 certified writes are correct, yet none of the 13 executions completes its task, which locates the remaining failures in target binding rather than write execution.

Critical strengths
  1. Problem framing. The paper clearly separates three questions: was the call admissible, is the task solved, and did this particular write produce its declared effect. The paper is careful about what its certificate does and does not guarantee.
  2. Principled qualification conditions. Independence of the witness from the mutation payload, completeness over paginated scope, version compatibility (Eq. 14–15), and frame conditions are the right ingredients, and they are stated precisely.
  3. Ablation design. The controlled interventions (Table 1) change one relation while holding the others fixed, so each requirement's role can be read off directly.
  4. Practical engineering details. Scope-aware invalidation avoids both stale acceptance (static reuse) and over-abstention (global invalidation). The graph is small in practice (median 4 nodes) with about 15% extra tool calls (Table 10).
Critical weaknesses
  1. The end-to-end baselines don’t fit the task, and key reference points are missing.

    The five external baselines (COLT, ToolRerank, ToolExpNet, AutoTool, and Self-Healing) are tool retrieval, selection, or routing methods. None was designed for agents acting in stateful environments, and none was evaluated on AppWorld or τ-bench in its original paper. The paper does not explain how these methods were adapted to AppWorld, which agent scaffold they run in, or how many samples each uses. The most relevant comparisons, meanwhile, are absent:

    • Closely related methods. The closest cited works (Cordon, SafeCommit, and ToolGate) are dismissed in a single sentence each, with neither a conceptual nor an empirical comparison.
    • Standard AppWorld agents. ReAct, PlanExec, and the other agents from the original AppWorld paper are not reported.
    • A single-sample native agent. The paper never reports a single candidate from the native pool without any selection. This is the most basic reference point, and it would show how much of the gain comes from sampling alone.
    • τ-bench. End-to-end results are reported only on AppWorld; τ-bench appears only in the certification analysis.
  2. The novelty of the concept is limited. The graph framing is mostly bookkeeping. The "dynamic graph" adds no algorithmic content beyond recording which read verified which write at which version and there is no learning component.

  3. The headline guarantee does not address the failure mode used as motivation. The introduction motivates DEG with "delete every song by an artist", where the agent modifies the wrong object or misses targets. By the paper's own definition (Eq. 12, App. A.3), the certificate holds only relative to the agent's bound target and "does not establish that the bound targets exhaust the user's intended target set." The claim actually certified ("the write hit the target the agent bound, and a fresh read-back shows the declared post-condition") which is fairly weak in deterministic sandboxes such as AppWorld and τ-bench, where a successful API call nearly always has its declared effect on its argument.

  4. The reference oracle for SCR is underspecified. SCR counts certificates "contradicted by an environment-level reference derived from benchmark state or evaluation artifacts" (App. B.1). It is unclear whether the reference is (a) the task evaluator, (b) the same contract post-condition evaluated on the ground-truth DB, or something else. If (b), DEG's 0% SCR is nearly tautological: a fresh, attributed read-back of a deterministic DB agrees with the DB. Table 1's attribution test shows the same pattern: DEG issues exactly the 38 reference-established certificates (FCR 0, FAR 0), which suggests the reference and DEG's criterion largely coincide.

Questions for authors
  1. How do Cordon (result lineage / semantic transactions), SafeCommit, and ToolGate differ operationally from DEG? Can any of them be run as a certification baseline?

  2. Define precisely the "environment-level reference" used for SCR. Is it independent of the contract post-conditions φ^post used by DEG?

  3. Can you explain Figure 1 a little bit more? CB claims are judged by the task-level evaluator (7/46 supported), and payload certificates are "none supported" (0/25). DEG's 13 certificates are drawn as fully "supported". What's the exact definition of "supported" here and how are they labeled?

  4. Why is full DEG the headline when count-only routing scores higher on both backbones? What concrete harm does "guard violation" capture outside a zero-by-construction diagnostic?

Reviewer_G23ZOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Dynamic Evidence Graphs (DEG), a framework for runtime certification of state-changing tool calls in LLM agents. DEG builds a graph during execution in which read/lookup calls are evidence nodes and write calls are effect nodes, connected by object-flow edges and verification edges (linking a write to its read-back). DEG certifies a write only if its target is traced from the task through fresh evidence without opaque nodes (LLM decisions), the write addressed exactly that target, and a read-back linked to the write satisfies the post-condition. For each task, DEG's execution runs alongside K = 4 independent native executions of the same model, and a router returns either DEG's execution or the best native one. The method is evaluated on τ-bench and AppWorld, reporting 0% observed contradicted certificates and higher pass rates than tool-selection baselines on AppWorld.

Critical strengths

The paper identifies an important problem in tool-using agents i.e. successful tool calls do not necessarily imply successful state changes and is worth exploring.

Critical weaknesses
  1. The gate only checks that each target has a fresh object-flow path from task evidence to the write with no opaque node on it. It never checks whether the lookups along that path returned the right objects. Even if a lookup is wrong, the resulting target may still have a valid path, so Gate = 1 and the write proceeds. Thus, the gate verifies target traceability rather than target correctness.

  2. Also the framework requires an LLM-generated task specification, from which the target bindings and object-flow edges are derived. Apart from saying that, the paper does not explain how the specification is produced (model, prompt, inputs) or how often it is wrong. This matters because a certificate only checks the targets the specification bound. It is also unclear who writes the per-tool contracts that define the post-conditions, and how much effort they take.

  3. Table 8 shows that most of the end-to-end gain comes from routing to native candidates as we see DEG's own execution scores 119/127 (Qwen/Gemini), compared with 127/154 with routing, and on Gemini it is well below the native-pool oracle (153). Certification is disconnected from task success as we see that none of the 13 certified held-out executions passed the full task, and certificate failures are not used to steer or improve the agent's execution.

  4. On AppWorld, DEG certifies only 4/50 (Qwen) and 7/50 (Gemini) executions, which is too small to make any solid conclusion.

  5. The end-to-end evaluation primarily compares DEG against tool-selection/retrieval baselines rather than methods that use test-time verification or verifier feedback.

Questions for authors
  1. What is the performance if the same LLM-generated specification is simply provided in the prompt, without DEG?

  2. What is the actual use of DEG certification if the underlying specification or an intermediate lookup can itself be incorrect?

  3. If the router selects a native run then there is no certification. What is the motivation for routing between the DEG and native executions ?

  4. Why aren't certification failures used as feedback to repair or steer the agent? How does DEG compare with test-time verification or verifier-guided steering methods under a matched inference budget?

  5. How are the LLM-generated specifications and per-tool contracts validated, and what are their error rates?

Reviewer_9joDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes DEG, a dynamic evidence graph for runtime certification of state-changing tool use by LLM agents: nodes represent evidence operations and effect instances; edges encode object-flow provenance and write-specific verification associations; node state carries scope/version metadata for temporal validity. Effect certificates are graph queries over connected target-write-witness subgraphs (C_i = Gate_i · WriteOK_i · WitnessOK_i · EffectOK_i), with candidate selection decoupled as a control layer. The evaluation covers certificate reliability across four evidence tiers on pooled tau-bench (580 executions, 251 certificates) and AppWorld dev50; controlled interventions isolating attribution, reachability, and temporal validity; evidence-sharing efficiency versus an EFFECT-RECORD control; end-to-end AppWorld execution against five baselines and a native-pool oracle; a graph-independent audit of 123 certified writes; and cross-backbone and runtime-profile analyses. Headline claims: 0% observed selective certificate risk (SCR) at 8.0-78.6% coverage (weaker tiers up to 28.6%), and end-to-end improvements of 35.1%/20.3% over the strongest external baselines.

Critical strengths
  1. A real, well-motivated problem attacked with unusually disciplined methodology: the Fig. 1 diagnostic (46 of 50 commit-blind completion claims, 7 supported) makes the tool-call-vs-effect gap vivid, and the controlled interventions (attribution, reachability, temporal validity), exact binomial CIs on all SCR entries (all recompute correctly), a graph-independent audit, and replay evaluation with the official evaluator are well above the norm for agent papers.

  2. Boundary honesty and properly isolated efficiency claims: Appendix A.3 states explicitly what a certificate does not establish, the pooled-CI caveat is disclosed, and the EFFECT-RECORD control isolates evidence sharing (87.7% acquisition-call reduction at fan-out 8; absolute footprint reported: median 4 nodes, 2.3 read-backs/task, about 15% extra tool calls).

Critical weaknesses
  1. The headline "0% observed SCR" is not supported as stated. On AppWorld — the flagship hard benchmark — DEG certifies only 4 (Qwen) and 7 (Gemini) of 50 executions, and the 95% CI upper bounds (60.2%/41.0%) never reach the abstract or conclusion; the strong instance (0/251, CI 1.5%) is pooled tau-bench dominated by the easiest cohorts. The abstention side is never analyzed (how many uncertified executions had fully correct effects is unknown), and the paper's own audit reports that none of the 13 DEG-certified executions passes the task-level evaluator — so certificates are rare exactly where they matter and do not guarantee task-level success.

  2. The paper's own ablation contradicts the end-to-end attribution, and the comparison set is mismatched. In Table 8, "w/o Read-back" leaves scores unchanged and "Count-only routing" (130/159) beats the full framework (127/154) on both backbones — a row Finding 12 ignores — so the Table 2 gains belong to the decoupled control layer, not the certification the paper is about. The five external baselines are all retrieval/selection methods (none performs trajectory selection), the oracle pool excludes eDEG, the closest verification systems (Cordon, SagaLLM, ToolGate) are cited but never compared, contract authoring cost is unquantified, and no code is available.

Questions for authors

Clarification questions (answers could change my assessment):

  1. What are DEG's execution-level false-abstention rates on AppWorld (how many of the uncertified 42-46 executions had fully correct realized effects)?

  2. Why do the abstract and conclusion cite "0% observed SCR" without the CI context of the 0/4 and 0/7 AppWorld instances, and is the SCR reference fully independent of DEG's read-back observations — would a wrong-but-consistent binding be counted as a false certificate?

  3. Why is the count-only routing result (130/159, beating full DEG) not discussed in Finding 12, and why was the weaker configuration used for Table 2? Please attribute the end-to-end gains to the control layer explicitly, or rerun Table 2 with the certification components removed to show their marginal value.

  4. None of the 13 certified executions in your audit passes the task-level evaluator — what should a user or downstream system conclude from a certified-but-failed execution, and what is the joint distribution of certification and task-level success across settings?

  5. How does DEG compare with Cordon's semantic transactions or ToolGate's contract verification under your certificate-reliability protocol?

  6. Why are the five external baselines all tool retrieval/selection methods rather than trajectory-selection methods, and what does a pool-matched oracle (including eDEG) score?

Additional concerns (for the record):

  1. How many tool contracts were authored, at what cost, and how sensitive are certificates to contract errors? What is the LLM specification mis-binding rate, and can it yield certified-but-wrong-target cases? Please release code and contracts.

  2. Please reconcile the payload-tier discrepancy between Fig. 1 (0/25 certificates supported) and the main analysis (1.4% SCR on tau-bench, 28.6% on AppWorld). Which external baselines received K = 4 pools and replay evaluation, and what explains the baselines' zero replay errors at much lower pass rates?

  3. The introduction's "0% observed SCR at 8.0-78.6% coverage, while weaker tiers reach up to 28.6% SCR" combines DEG's thinnest-evidence setting (AppWorld, 0/11 pooled, CI about 28.5%) with the largest baseline failure in one comparison — please quote per-setting contrasts with intervals. The coverage range spans an order of magnitude and its top end comes from the easiest tasks (and N = 14).

  4. In Fig. 3c, relaxing DEG's read-back requirement admits 39 executions with 32 falsely certified, versus 29 all-false for the relaxed PL threshold — in absolute terms the relaxed DEG rule produces more false certificates; please report absolute counts alongside the relative rates in Finding 2.

  5. What happens to read-back witnessing when read-backs are paginated, rate-limited, or state-changing? How often did post-issuance frame-condition violations occur, and should consumers treat certificates as expiring?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.