State-Centric Decision Process

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.

📋 한 줄 요약

**[LLM Agents / 의사결정 프레임워크]** 언어 환경에서 MDP 분석에 필요한 구조를 에이전트가 술어 단위로 직접 구성하는 State-Centric Decision Process(SDP) 제안.

🎯 핵심 기여도

웹 브라우저·코드 터미널·인터랙티브 시뮬레이션 같은 언어 환경에 MDP 구조(상태 공간·관측 매핑·인증 전이·종료 조건)가 부재하다는 문제 정식화.
에이전트가 자연어 술어를 행동·관측과 함께 만들어 인증된 상태(certified state)를 누적하는 SDP 런타임 도입.
상태 공간·관측 매핑·인증 전이·종료 조건 네 가지를 SDP 런타임이 자동 구성.
5개 벤치마크(plan·과학탐사·웹 추론·multi-hop QA)에서 모든 training-free 최고 결과 달성, horizon이 길수록 우위 확대.

💡 핵심 아이디어

언어 환경은 상태가 명시적으로 주어지지 않는다. 에이전트가 매 스텝 "세상이 어떻게 보여야 하는지"를 자연어 술어로 약속하고 행동 후 관측으로 검증하면, 그 술어들의 누적이 사후적으로 MDP 구조를 제공한다.

🔬 기술적 접근법

**모델/방법론**: 자연어 술어 기반 인증 상태 누적 런타임 SDP.
**핵심 기법**: 매 스텝 술어 제출 → 행동 → 관측 대조, 통과 시 certified state로 채택, 누적된 trajectory가 task-induced 상태 공간·관측 매핑·인증 전이·종료 조건을 함께 제공.

📊 주요 결과

5개 벤치마크 모두에서 training-free SOTA, horizon이 길수록 격차 확대.
credit assignment, failure localization, partial-progress 측정, 모듈러 operator 교체 등 reactive agent에서 불가능한 분석 가능.
planning, 과학 탐사, 웹 reasoning, multi-hop QA 등 광범위 일반화.

💭 의의 및 한계

**의의**: LLM 에이전트 평가·디버깅·운영을 위한 명시적 구조 기반을 제공해 reactive 에이전트의 한계를 우회. **한계**: 술어 생성 품질이 LLM 능력에 강하게 의존, 술어 검증의 인식적 비용·신뢰성은 분석 과제.

🚀 실용적 활용

웹 자동화 에이전트의 audit 가능한 trajectory 기록.
디버깅 가능한 LLM 기반 RPA 시스템.
과학 탐사·코드 에이전트의 step-level 진단 도구.