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.
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2605.12755 [cs.AI] |
| (or arXiv:2605.12755v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2605.12755 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Sungheon Jeong [view email]
[v1]
Tue, 12 May 2026 21:09:43 UTC (2,315 KB)