- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
SDP represents goals as natural-language predicates and organizes execution through Propose, Realize, Validate, and Replan. Validation can certify consecutive goals; after failure, replanning preserves the certified prefix. The paper connects these records to MDP analysis and evaluates task performance, cost, and validation behavior on five benchmarks.
Critical strengths
- Inspectable execution. Explicit predicates, consecutive-goal validation, and failure recovery divide long trajectories into units with identifiable validation depth and failure locations. This is useful for debugging agents.
- Targeted empirical support. Three-run comparisons using GPT-4o support the stricter execution procedure over lighter prompting. Cost, latency, and injected verifier-error experiments provide further engineering evidence.
Critical weaknesses
- Conflicting protocol descriptions leave comparability unclear. Table 5 and Appendix B.4 describe MuSiQue retrieval over about five million Wikipedia paragraphs. Appendix A.6 and Table 12 instead specify about 84,000 paragraphs and use true hop counts from task IDs. Both corpus size and hop information affect difficulty. It is unclear whether this is a reporting error or a substantive protocol difference.
- The formal claim needs a clearer execution boundary. The paper explicitly states that Proposition 1 assumes environmental conditional independence. After Replan reads the full history and changes the plan tail, the decision point and conditioning state in Eq.7 remain unclear. Validation failures also do not establish that all violations of state sufficiency are detected. Since AdaPlanner already checks subgoals and replans after failure, the added capabilities of SDP's predicate interface also need to be stated precisely.
Questions for authors
- Evaluation protocol: Which corpus, examples, and hop information underlie the MuSiQue results in Tables 5–6 and Appendix C? Which baselines share these conditions, and which main comparisons remain valid under a common protocol?
- Formal scope: Please define the decision points, plan tail, and conditioning variables in Eq.7 before and after Replan. Which properties are enforced by the implementation, and which rely on environmental assumptions? Clarify the resulting extension over AdaPlanner.
3 comments
Response for dLLh comment
Thank you for taking the time to read our response and for your valuable feedback. We appreciate the opportunity to state clearly what distinguishes SDP.
The State-Centric Decision Process (SDP) places the state at the center of the process, and each state is a condition that names no action. The plan is a sequence of such states, written as natural-language predicates , and it lists no actions. During execution, Realize selects an action for the next predicate, and Validate tests the resulting observation against the remaining predicates. In AdaPlanner the plan is executable code that, for each subgoal, lists the actions to execute and ends with an assertion that tests whether the subgoal is fulfilled. Both methods check intermediate goals and revise the plan on failure. The difference is that a predicate in SDP has three roles. It is an element of the plan, it is what Validate tests, and once certified it is the state from which the next action is selected.
The contribution is that the plan contains no actions, so actions are selected and replaced without rewriting it. This has three concrete effects.
- A rejected action does not change the plan. Realize selects a different action for the same predicate. Replan replaces the remaining predicates only after the attempt budget is exhausted.
- The plan can be written without knowing which actions will work. Writing a predicate requires neither an action sequence nor a predefined state schema.
- Progress is counted in certified predicates. If one observation satisfies consecutive predicates, the plan advances by . Every run records whether the goal predicate was certified.
Two further properties hold in every environment.
-
Every run leaves a record of certified states. Each certification appends the certified state and the action that produced it, so a run ends with the sequence below. The analyses in Section 4.2 are computed from this record (Figure 2).
-
From each decision point in Proposition 1, Realize and Validate do not read the history before it. Realize reads only , and Validate reads only the remaining predicates and the new observation. A call therefore carries about 1.0k tokens on MuSiQue, against 4.6k for ReAct (Appendix C).
The Markov property of this record with respect to the environment is Proposition 1 (ii) and requires an assumption on the environment. Nothing in this response uses it.
Existing evidence for each effect. The evidence below comes from Section 4.
1. A valid plan is not discarded because of a wrong action. Because the plan contains no actions, a rejected action leaves the plan unchanged. Realize selects another action for the same target, excluding the actions already rejected, and Replan is called only after the attempt budget is exhausted. In AdaPlanner a failed assertion regenerates the plan code. On AssistantBench, roughly 40% of certified steps required at least one rejection and retry before certification (Section 4.1).
2. The plan is written without knowing the actions. Because the plan contains only predicates, Propose writes it from the initial state and the goal, without specifying an action sequence. In AdaPlanner's main setting the plan is written against an authored state interface with task-specific demonstrations, and the paper lists reliance on demonstrations as a limitation. SDP runs with zero-shot prompts and the same execution loop (Algorithm 1) (Section 4.1).
3. One action can advance the plan by several targets. Because the plan is a sequence of predicates, Validate tests one observation against the remaining predicates and advances the plan by the number of consecutive predicates, counted from the next one, that it satisfies. In AdaPlanner the actions of each step execute before its assertion is tested, so a step is not skipped when its condition already holds. Advances with account for 19% to 41% of all advances on four benchmarks (Figure 2a), and capping the advance at lowers all five benchmarks by 4.3 to 12.0 points (Table 7). Runs with a certified goal are correct 77% and 62% of the time on HotpotQA and MuSiQue, against 40% and 19% for runs that end in forced finalization (Figure 2d).
Summary. The contribution beyond assertion-based planning is that SDP is state-centric. The plan is a sequence of states and contains no actions, and actions are selected during execution to make each state hold. Three effects follow from this separation. A valid plan is not discarded because of a wrong action, the plan is written without knowing the actions, and one action can advance the plan by several targets. None of the three occurs under the mechanism described in the AdaPlanner, where the plan contains the actions. The existing evidence shows that these effects occur in SDP runs.
Thanks for explaining how separating predicates from actions supports retries and cascade progress. Together with the corrected MuSiQue comparisons and the narrower formal claims, this gives me enough support for weak acceptance (3). I view the contribution primarily as a useful execution framework. Please keep the theoretical and compute-related limitations explicit, and ensure the revised tables support the numerical claims in the response.
Thanks for the reruns and clarifications. These largely address my protocol concern. My remaining concern is the contribution beyond assertion-based planning such as AdaPlanner. The structural differences are clearer, but the ablations establish their utility within SDP, and the Markov interpretation still relies on environmental sufficiency. Could you explain what the existing evidence establishes beyond this prior approach?