acceptodds
Under review as a conference paper at ICLR 2027

EvoPlanner: Decoupling Evidence Obligations from Evolving Task Graphs for Reliable Tool Use

Abstract

Reliable tool use depends on maintaining a coherent account of what the original request still requires as an agent revises its plan. Structured planners organize dependent actions, and verification-guided methods assess intermediate outputs, yet task-level status alone cannot express which parts of a request remain supported after a task is split or replaced. An incomplete task may already have obtained useful evidence; retaining its output does not by itself preserve an explicit link to the requirements that evidence satisfies. We present EvoPlanner, which separates fixed queries-derived evidence obligations from an evolving Task DAG. Accepted observations are linked to these obligations through persistent Witnesses, and unmet obligations guide bounded revisions to unresolved tasks. This design preserves the recorded support across task replacement while allowing the acquisition strategy to change. In StableToolBench, EvoPlanner achieves macro-average SoPR scores of six-subsets of and with Qwen-Long and DeepSeek V4 Flash, exceeding our corresponding VeriMap reproductions by and percentage points. Together with the component ablations, these results support integrating evidence verification with dynamic plan revision, enabling agents to adapt their execution while retaining acquired support and improving task completion.

Primary area:
interpretability and explainable AI
Keywords:
LLM agents, tool use, evidence tracking, dynamic planning, verification

Reviews

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

EvoPlanner separates what a user’s request requires from the evolving plan used to fulfill it. It maintains fixed evidence obligations, a revisable task DAG, and a persistent ledger of verified observations called Witnesses. This allows useful evidence from partially completed tasks to survive task replacement and guide subsequent execution. On StableToolBench’s 765 solvable queries, the system improves macro-average SoPR over the authors’ VeriMap adapters by 10.8 and 17.0 percentage points with two backbones. Ablations and a repair-budget study provide additional evidence for the integrated framework.

Critical strengths

A useful separation of requirements, execution, and evidence. Task success is often too coarse to represent partial progress. EvoPlanner makes this distinction explicit and provides a concrete way to preserve and reuse supported information after replanning. This is a meaningful contribution to the design of tool-using agents.

Substantial gains across both evaluated backbones. EvoPlanner outperforms the corresponding local CoT and VeriMap configurations on all six subsets. The improvements are large overall, and disabling graph revision reduces I3 Inst performance by 9.8 points. These results make the integrated approach promising, even though the source of the gains remains uncertain.

Critical weaknesses

The central contribution is not isolated experimentally. Removing the evidence layer also removes dynamic repair, so this ablation cannot establish the value of persistent support links. There is no direct measurement of evidence reuse or support accuracy. Furthermore, equal tool-call ceilings do not control model computation, and the VeriMap adapter replaces generated Python verification with LLM checks. Consequently, the results do not establish whether the proposed representation improves over a faithful baseline given comparable inference resources.

The evaluation leaves important uncertainty about reproducibility and generalization. The component studies use only 61 development-exposed queries, with one generated answer per query and condition. Repeated judging does not measure agent variability. Section 5 also mentions a different judge for the controlled study without clearly identifying it, while Appendix A.3 leaves historical model routing and auxiliary-component settings unspecified. These gaps make it difficult to determine exactly what produced the reported improvements.

Questions for authors
  1. Which models and auxiliary components were used in each reported configuration? Please also clarify the judge used for the component studies and how the 61 I3 Inst queries influenced development.

  2. Can you isolate persistent Witness links while retaining the same repair, verification, and synthesis components—for example, by comparing against a system that preserves raw observations but reconstructs their requirement links after revision? How often does retained evidence actually enable successful continuation?

  3. What are the token and model-call costs of the local baselines? Does the advantage remain against a faithful VeriMap implementation or a retry baseline with comparable inference cost?

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

The paper proposes EvoPlanner, a tool-use framework that separates fixed query-derived requirements from a revisable task graph. Verified tool observations are stored as persistent Witnesses, allowing acquired evidence to remain associated with requirements when tasks are replaced. Unmet requirements guide subsequent replanning. Experiments on StableToolBench report improvements over CoT and the authors’ VeriMap adapter, alongside component ablations and a repair-budget study.

Critical strengths

The distinction between task completion and requirement satisfaction is conceptually clear, and the framework explicitly preserves useful results from partially completed tasks. The full system improves reported performance across all six StableToolBench subsets with both evaluated backbones. The paper also acknowledges important limitations of its evaluation and model-based verification.

Critical weaknesses
  1. The central motivation is insufficiently established. The paper does not demonstrate that capable LLM agents frequently lose track of satisfied requirements or fail to reuse partial results when their interaction history remains available. A model could potentially infer these relationships from history, possibly assisted by a lightweight memory recording completed requirements, supporting results, and outstanding work. The absence of explicit requirement–evidence links does not itself establish a practical limitation. However, the paper provides neither a direct comparison against this simple alternative nor a quantitative analysis of the failures motivating its architecture. The partial-success example in Section 3.3 is explicitly constructed rather than an observed benchmark trajectory. I am therefore unconvinced that the proposed complexity is necessary.

  2. The evaluation does not connect the reported improvements to the proposed mechanism. All experiments use StableToolBench with an eight-tool-call ceiling per query, without characterizing how frequently these tasks require preserving partial evidence across substantial plan revisions. There is no evaluation in additional agent environments that directly tests these challenges. More importantly, Section 4.2 explicitly acknowledges that the aggregate scores neither measure evidence reuse nor establish that reuse caused the gains. The ablation removing the evidence layer also removes dynamic repair, while equal tool-call ceilings leave inference effort unmatched. Additional verification, replanning, and final-answer checks therefore remain alternative explanations for the improvements. The results demonstrate gains for the complete system, but do not establish that persistent requirement–evidence links address a significant failure mode or outperform simpler memory-based approaches at comparable cost.

Questions for authors
  1. What fraction of baseline failures can be attributed specifically to losing or failing to reuse partial evidence after replanning? Can the authors provide observed trajectories and quantitative evidence showing that this is a recurring limitation of capable agents with access to their interaction history?

  2. Does EvoPlanner retain a meaningful advantage over the same backbone using a lightweight progress memory under comparable inference budgets? A comparison that keeps verification and repair opportunities comparable while varying the evidence representation would materially affect my assessment of the framework’s necessity.

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

EvoPlanner proposes an evidence-guided planning framework for reliable tool use. The key idea is to decouple fixed, query-derived Evidence Obligations from a dynamically evolving Task DAG. A Semantic Commit mechanism verifies tool observations and stores accepted evidence as persistent Witnesses, allowing the agent to preserve acquired support even when incomplete tasks are replaced or revised.

The framework is evaluated on six StableToolBench subsets using Qwen-Long and DeepSeek V4 Flash. It achieves macro-average SoPR scores of 50.4% and 62.2%, outperforming the corresponding VeriMap adaptations by 10.8 and 17.0 percentage points. Component ablations and repair-budget experiments further demonstrate the benefits of the integrated framework.

Critical strengths

Clear and meaningful problem formulation. The paper identifies a practical limitation of task-centric planning: useful evidence can be acquired even when its producing task remains incomplete. Separating task completion from requirement satisfaction is a well-motivated design.

Coherent framework design. Fixed Evidence Obligations, persistent Witnesses, Semantic Commit, and dynamic DAG revision form a reasonably well-integrated architecture. The separation between control dependencies and evidence dependencies is particularly useful.

Promising empirical improvements. EvoPlanner consistently outperforms its local CoT and VeriMap baselines across all six StableToolBench subsets and both evaluated backbones.

Critical weaknesses

Insufficient Validation of the Core Contribution. The experiments do not directly evaluate Witness persistence or evidence reuse. The ablation removes the evidence layer and dynamic repair together, making it difficult to isolate the contribution of the proposed mechanism.

Unmatched Computational Budgets. Although the methods share the same tool-call limit, model calls and token budgets are not matched. The reported improvements may partly result from additional inference effort rather than the proposed framework.

Potentially Unfair VeriMap Baseline. The authors replace VeriMap's original Python-based verification with LLM-based checks without validating the modified implementation. This raises concerns about the fairness of the comparison.

Limited Evaluation on SOTA Models. EvoPlanner is evaluated only with Qwen-Long and DeepSeek V4 Flash. Experiments with stronger state-of-the-art reasoning and tool-use models would better demonstrate its generalizability.

Insufficient Verification Reliability Analysis. The paper does not directly evaluate the accuracy of Semantic Commit or Evidence Obligation extraction. Incorrect judgments could undermine the reliability of persistent Witnesses.

Limited Experimental Robustness. Experiments are restricted to StableToolBench, with ablations on only 61 queries. Moreover, repeated GPT-4o judgments of fixed answers do not establish run-to-run reliability.

Questions for authors

Could the authors provide a separate ablation of Witness persistence and quantify how frequently evidence is reused across task revisions?

Could the authors clarify why VeriMap's original Python-based verification was replaced with LLM-based checks and provide comparisons under matched inference budgets?

Could the authors evaluate whether the improvements hold across independent runs and stronger SOTA backbones?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.