acceptodds
Under review as a conference paper at ICLR 2027

State-Centric Decision Process

Abstract

Language environments such as web browsers, code terminals, and interactive simulations emit raw text rather than states, and provide none of the runtime structure that MDP analysis requires. No explicit state space, no observation-to-state mapping, no certified transitions, and no termination criterion. We introduce the State-Centric Decision Process (SDP), a runtime framework that constructs these missing inputs by having the agent build them, predicate by predicate, as it acts. At each step the agent commits to a natural-language predicate describing how the world should look, takes an action to make it true, and checks the observation against it. Predicates that pass become certified states, and the resulting trajectory carries the four objects language environments do not provide, namely a task-induced state space, an observation-to-state mapping, certified transitions, and a termination criterion. We evaluate SDP on five benchmarks spanning planning, scientific exploration, web reasoning, and multi-hop question answering. SDP achieves the best training-free results on all five, with the advantage widening as the horizon grows. The certified trajectories additionally support analyses unavailable to reactive agents, including per-predicate credit assignment, failure localization, partial-progress measurement, and modular operator replacement.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, agentic planning, decision process

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_dLLhOpenReview ↗
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

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?

AuthorsOpenReview ↗

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 (s^1,…,s^n)(\hat{s}_1, \ldots, \hat{s}_n), 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.

  1. 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 bb is exhausted.
  2. The plan can be written without knowing which actions will work. Writing a predicate requires neither an action sequence nor a predefined state schema.
  3. Progress is counted in certified predicates. If one observation satisfies kk consecutive predicates, the plan advances by kk. Every run records whether the goal predicate gg was certified.

Two further properties hold in every environment.

  1. 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). (s0,a0,st1,at1,…,aT−1,sT)\bigl(s_0, a_0, s_{t_1}, a_{t_1}, \ldots, a_{T-1}, s_T\bigr)

  2. From each decision point in Proposition 1, Realize and Validate do not read the history before it. Realize reads only (st,s^t+1,ft)(s_t, \hat{s}_{t+1}, f_t), 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 bb 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 kk 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 k≥2k \geq 2 account for 19% to 41% of all advances on four benchmarks (Figure 2a), and capping the advance at k≤1k \leq 1 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.

Reviewer_eytbOpenReview ↗
Rating
3(+1)
Confidence
3(−1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes and implements a novel agentic harness that consists of 4 steps - proposing a decomposition of a plan into smaller subgoals, realizing each subgoal by prompting for an executable action for it, validating the execution of the action on the environment, and replanning the subgoal predicates in case the validation fails. These steps occur in a strict loop (Algorithm 1). They show that this protocol called SDP outperforms other baseline agent designs on 5 diverse benchmarks spanning planning, multi hop question answering, scientific exploration, web reasoning.

Critical strengths
  1. Impressive results: The paper compares many baseline agents across 5 diverse benchmarks and show that SDP beats these other agent designs.
  2. Table 6 provides a good ablation study of how each phase of the SDP protocol is found to be necessary by the authors to achieve strong performance.
Critical weaknesses
  1. Incremental update in the agent design: The idea of goal decomposition and verification of executors is not entirely new. Another work with a similar design is done by Xu e.t al.[1]. Comparisons to such baselines that perform the same steps as SDP but perhaps not with the exact same formal implementation seem to be missing in the paper, which leads to confusing results - is SDP better because it attempts task decomposition and verification as opposed to a simpler baselines like ReAct or Plan-and-Act, or is it better than other existing works which perform task decomposition
  2. Potential leak of benchmark related informations?: As mentioned in Q1, TravelPlanner seems to use the benchmark's evaluator to select which sub tasks to realize. This makes me wonder if the settings the benchmarks are run are matched between SDP and other baseline agent results reported in the paper. Other examples: a. ScienceWorld: the validator sees the score change (A.3, “Realize and Validate,” page 16) b. ScienceWorld: much larger step budget (Table 9). SDP gets 30 attempts per predicate and a 500-step global cap. The Table 4 baselines are copied from papers using the standard protocol’s step limits, so SDP may simply have more interactions with the environment. c. MuSiQue: retrieval corpus mismatch (Table 5 caption and B.4 vs A.6 and Table 12). Table 5 and B.4 say BM25 over a 5M-paragraph Wikipedia corpus. A.6 and Table 12 say about 84K paragraphs drawn from the MuSiQue splits themselves. That small corpus comes from the dataset’s own contexts, so gold paragraphs make up a much larger share of it, and retrieval is far easier than over 5M. d. AssistantBench: after two rejections, a finding with “substantive content” is accepted anyway (A.4), which bypasses the certification the paper’s whole framing rests on.
  3. Does SDP's benefit generalize to stronger models?: It is unclear whether the paper's formalization of agents brings significant advantages to much stronger frontier models like Claude Opus >4, GPT >5.5 etc. or not.
  4. Backtracking between validating multiple sub-goals: The paper does not address how to handle backtracking / undoing of states, ie, in case a predicate is VALIDATED and found to be wrong, but performs a destructive action in the process does it stop the whole task from progressing? Does this warrant a verification of the plan even before the REALIZE phase?
  5. Tables 2,3,4 do not use same LLM backbones for all rows. This makes the baseline numbers hard to compare and rank.

[1] - Verification-Aware Planning for Multi-Agent Systems (https://arxiv.org/pdf/2510.17109)

Questions for authors
  1. L792: Mentions that "Before each REALIZE call, the adapter presents the candidate options that pass the deterministic constraint checks of the official evaluator given the current state, including local constraints, transport-mode consistency, trip-wide uniqueness of restaurants and attractions, and remaining budget". a) the VALIDATE phase is expected to occur only after REALIZE call. Do the SDP agents for other benchmarks also conduct similar pre-validation checks? b) This means the SDP agent uses the gold evaluators to infer some information and filter out incorrect predicates early-on. The other baselines evaluated might not have had similar checks making the comparison not be apples to apples.
  2. TDP is a close baseline to SDP since it does hierarchical decomposition and is also a recent work. They show results on TravelPlanner, ScienceWorld, and HotpotQA. Thus, can we show the results for TDP in Tables 4 and 5 as well? Also, the final pass rate for
  3. Can more recent and powerful agent designs like Browser-Use (https://github.com/browser-use/browser-use) and GenericAgent (https://github.com/ServiceNow/AgentLab) be evaluated as well for AssistantBench? These agents perform task decomposition and verfiication steps as well, and are recent compared to baselines like ReAct.
  4. Are the baselines listed in the paper matched on the token and retry budget that SDP agents get? Were the numbers for the baselines rerun by the authors?
  5. What model is used for Table 7?
6 comments
AuthorsOpenReview ↗

Response for Question 1

Thank you for reading the appendix this closely. You read L792 correctly, and we apologize for the confusion this design caused. The revision removes the filter. We rebuilt the TravelPlanner adapter so that no operator takes anything from the evaluator, and we reran SDP together with every baseline under one protocol. We answer your two points in turn.

(a) Checks before Realize. In the revised implementation no adapter runs a check before Realize, on any benchmark. The order is always the one of Algorithm 1: Realize proposes an action, the environment answers it, and Validate judges the answer. No operator reads an evaluator, a gold answer, or a score. The table lists what Validate reads on each benchmark.

BenchmarkChecked before RealizeWhat Validate reads, after the actionEvaluator, gold answer, or score visible to an operator
TravelPlannerNothingEntries absent from the given information are rejected by lookup. Otherwise an LLM verdict from the query, the action, and the cost enquiry of the environmentNo
ScienceWorldNothingActions the simulator does not recognize are rejected. Otherwise an LLM verdict from the observationNo
AssistantBenchNothingAn LLM summarizes the retrieved evidence into a finding, and a second LLM call judges whether it addresses the stepNo
HotpotQA, MuSiQueNothingExplicit non-answers are rejected by rule. Otherwise an LLM verifier checks the finding against its cited paragraphNo

On TravelPlanner specifically, Realize now receives the task prompt, the certified state, the target predicate, and the attempts rejected at that target, and it chooses entries from the full information given with the query. Nothing is filtered or ranked for it. The goal predicate is certified by the same LLM verdict as every other predicate. The official evaluator is called once, on the submitted plan, and its result is never returned to the agent.

(b) A like-for-like comparison. In the revision all six methods are run by us, and they share everything except the method itself.

ItemSetting, identical for every method
Mode and queriesOfficial sole-planning mode, 180 validation queries
BackboneGPT-4o
Task promptThe instruction of the official sole-planning agent, its worked example of the output format, the given information, and the natural-language query
EnvironmentThe cost enquiry of the official sole-planning environment, and one final submission
ScoringOfficial commonsense and hard constraint evaluators, aggregated as in the official script
Withheld from every methodThe structured annotation of the query (budget, number of travelers, local constraints), any list of the constraints the evaluator checks, and the result of the evaluation

The last row follows the rules of the official repository, which rule out structured versions of the query and hand-written cues about the evaluation. ReAct follows the official agent with at most 30 steps. Reflexion runs three trials and reflects on the cost enquiry of the plan it submitted. Plan-and-Solve, GoalAct, and TDP submit once.

MethodDeliveryCommonsense MicroCommonsense MacroHard MicroHard MacroFinal Pass
ReAct97.281.926.758.830.66.7
Reflexion100.087.436.751.926.17.2
Plan-and-Solve100.087.338.947.920.03.9
GoalAct100.075.411.144.521.75.6
TDP100.079.021.739.327.83.3
SDP100.088.530.659.033.314.4

This is the comparison you asked for. Without any evaluator information, SDP has the highest Final Pass Rate, 14.4% against 7.2% for the next best method, together with the highest Hard Constraint rates and the highest Commonsense Micro rate. The advantage comes from checking each decision against the cost and the records returned by the environment before the plan advances, so a violation surfaces at the step where it arises and not after the itinerary is assembled.

Your concern also led us to check the settings of the other benchmarks one by one. We are grateful for this comment, since it made the TravelPlanner comparison much stronger.

Revision.

  • Appendix A.2: the description of the TravelPlanner adapter is rewritten, and the candidate filter of the submission is removed.
  • Appendix A.1: the validation modes are restated, with the deterministic rules that remain on each benchmark.
  • Table 2 and Section 4.1: all six methods are rerun by us on GPT-4o under the protocol above.
  • Appendix B.1: the evaluation protocol and the baselines are stated for the sole-planning mode.
  • Tables 6 and 7, Figure 2, and Appendix C: the TravelPlanner entries are recomputed from the new runs.
AuthorsOpenReview ↗

Response For Question 4

Thank you for raising this. Both parts have a direct answer, and the revision now states them in the paper.

Which numbers are rerun by us. On three benchmarks every baseline is run by us under the same conditions as SDP. On the other two we compare against the published numbers of the standard protocol.

BenchmarkBaselinesSourceShared with SDP
TravelPlannerReAct, Reflexion, Plan-and-Solve, GoalAct, TDPRun by usGPT-4o, task prompt, environment, 180 validation queries
HotpotQA, MuSiQueNo retrieval, ReAct, IRCoT, Plan-and-Act, VeriMAP, TDPRun by usGPT-4o, BM25 index and corpus, 500 test questions
ScienceWorldSayCan, ReAct, CoT, Reflexion, EvoAgent, Plan-and-ActPublished numbersGPT-4, standard 30-task protocol, simulator step limit of 100
AssistantBenchSeven systems of the official leaderboardOfficial leaderboardTest split and scoring

Token and retry budget. We fix everything that defines the task, namely the backbone, the tools and retriever, the task prompt, the questions, and the step limit of the environment. Within that, each method runs with the budget its own design prescribes. ReAct on TravelPlanner follows the official agent with at most 30 steps, Reflexion runs its three trials, and IRCoT uses the hyperparameters selected by its own protocol. Forcing one token count on methods that differ in how they spend it would change the methods themselves, so we report what each one spends next to its score.

MethodHotpotQA CallsTok. (k)MuSiQue CallsTok. (k)
ReAct3.76.726.630.37
IRCoT3.330.583.934.28
Plan-and-Act8.019.5712.456.27
VeriMAP14.623.7817.433.59
TDP11.826.7313.645.44
SDP12.88.9824.825.45
Method (TravelPlanner)Final passCallsTok. (k)
Plan-and-Solve3.91.07.0
Reflexion7.25.035.7
GoalAct5.69.664.5
ReAct6.78.283.3
TDP3.329.3193.3
SDP14.493.8431.2

On the QA benchmarks the gain is not bought with compute. On MuSiQue, SDP has the highest EM and F1 while spending fewer tokens than every other retrieving method, and on HotpotQA it spends less than a third of IRCoT. On TravelPlanner the Final Pass Rate of the baselines does not rise with their budget. TDP spends 193.3k tokens and has the lowest rate, while Reflexion reaches 7.2% with 35.7k over three trials. SDP spends more there because every decision is validated against the environment, and it reaches twice the best baseline.

On ScienceWorld, SDP now runs under the same simulator step limit of 100 as the published baselines, with zero-shot prompts, and uses 68.7 calls and 82.2k tokens per task. On AssistantBench the baselines are leaderboard entries, and SDP uses 18.2 calls and 35.3k tokens per task.

Revision.

  • Section 4 and Appendix B state, for each benchmark, which baselines are run by us and which are published numbers.
  • Table 5 reports LLM calls and tokens for every method.
  • Appendix A states the attempt budget, the replan limit, and the step limit of SDP on each benchmark, and Appendix C.1 reports its cost per operator.
AuthorsOpenReview ↗

Response For Question 5

Table 7 uses GPT-4 on ScienceWorld and GPT-4o on the other four benchmarks, the same backbones as the main results. The revision states this in Appendix C.1, and Sections 4.3 and 4.4 refer to it.

Reviewer_Kix7OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes the State-Centric Decision Process (SDP), a runtime protocol for LLM agents operating in language environments. SDP decomposes execution into four operators: PROPOSE, REALIZE, VALIDATE, and REPLAN. The agent first generates a sequence of natural-language predicates, executes actions to satisfy the next predicate, validates the resulting observation, and retries or replans when validation fails. Successful predicates are recorded as certified states, yielding structured trajectories with state transitions, cascade depth, partial progress, and failure locations.

The method is evaluated on five benchmarks: TravelPlanner, AssistantBench, ScienceWorld, HotpotQA, and MuSiQue. SDP reports strong training-free performance across all five benchmarks, with particularly large gains on longer-horizon tasks. Matched-backbone experiments, component ablations, and validator-error injection studies are used to analyze the contributions of validation, replanning, and cascade handling.

Critical strengths
  1. The paper presents a clear and coherent execution protocol that separates planning, action realization, validation, and replanning. This separation provides useful trajectory-level diagnostics, including failure localization, partial-progress measurement, and cascade analysis, which are difficult to obtain from purely reactive agents.
  2. The empirical study is broad and reasonably well structured. The method is evaluated across five substantially different benchmarks, and the matched-backbone comparisons, component ablations, and validator-error injection experiments provide useful evidence that validation and replanning contribute to the reported gains, especially on longer-horizon tasks.
Critical weaknesses

1. The claim about “certified states” needs to be more precise

The paper seems to use the term “certified states” too broadly.

  • On four of the five benchmarks, VALIDATE relies mainly on an LLM’s judgment.
  • These judgments do not come from environment-provided ground-truth states or transitions.
  • In this sense, the outputs are closer to model-judged claims or protocol-level certifications than environment-certified states.
  • The reported validator errors also raise concerns about this interpretation. For example, the later-rejection rate on AssistantBench is relatively low, suggesting that some incorrect states may still be accepted.

The theoretical discussion also needs more justification. Proposition 1 assumes that the environment is Markovian. However, the locality of the agent operators does not by itself establish this assumption. The paper should explain whether this assumption holds for the evaluated environments and what happens when it does not.

2. The comparisons are not fully matched in terms of compute and protocol

The main comparisons do not fully control for the experimental protocol or computational budget.

  • The headline tables combine results from different papers, backbones, tools, and retrieval systems.
  • Under the matched protocol, SDP is mainly compared with ReAct.
  • SDP also uses substantially more LLM calls and tokens.

For example, on ScienceWorld, SDP uses approximately 177k tokens per task, while ReAct uses about 17k tokens. This is a large difference.

Therefore, it is difficult to determine how much of the improvement comes from the proposed state-centric design and how much comes from additional verification, retries, or computation. The paper would be stronger if it included comparisons under equal token budgets, equal numbers of LLM calls, or similar computational costs.

3. The paper should distinguish task success from validator success

The current evaluation does not clearly separate actual task completion from successful validator decisions.

A goal predicate may be accepted by the validator even when the final answer or task outcome is incorrect. This issue is particularly important because some experiments use forced finalization.

I suggest reporting the following results separately:

  • End-to-end task success rate;
  • Validator precision and recall;
  • The fraction of cases accepted by the validator but ultimately incorrect;
  • Performance under equal token or call budgets;
  • Results with and without forced finalization.

These analyses would clarify whether SDP mainly improves task execution, or whether it primarily improves state verification and process control.

Questions for authors
  1. Can you provide a more strictly controlled comparison against ReAct and stronger planning or retrieval baselines using the same backbone, tools, retrieval method, token budget, and maximum number of environment interactions? How much of the gain remains after normalizing for the substantially larger SDP compute budget?

  2. For each benchmark, how are VALIDATE decisions evaluated against ground truth? Please report validator precision, recall, false-positive and false-negative rates, and the relationship between goal certification and actual task success. In particular, how should the low later-rejection rate on AssistantBench be interpreted?

  3. Given that Proposition 1 assumes that the environment response depends on the history only through the current certified state and plan tail, what empirical or formal evidence supports this assumption? Would the authors consider weakening the claim from constructing an MDP state space to constructing a useful, auditable predicate-based execution trace?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.