Most LLM-agent pipelines organize past interactions into memory but still lack a coherent, actionable picture of the current world. The key insight of this work is that an explicit, task-conditioned belief state—paired with continual consistency checks and online diagnosis of unproductive behavior—makes inference-time decisions far more reliable for long-horizon tasks.
Key Findings
- Consistent belief states: Representing the world state plus epistemic and achievement gaps lets the agent know both what it believes and what remains unknown or undone, making planning decisions actionable rather than history-driven.
- Trapping-aware recovery matters: PoS detects Belief Trapping via gap persistence, progress stagnation, and belief recurrence, then composes recovery constraints tailored to the trapping pattern and gap type to restore goal progress.
- Empirical gains across tasks: With three LLM backbones on four benchmarks (ALFWorld, LOCA-Bench, RCA-100, ClinDiag), PoS yields consistent improvements (up to +22.68% on ALFWorld and +37.89% on RCA-100 joint accuracy) while remaining robust as context grows.
- Cost–benefit tradeoff: PoS uses more inference tokens for explicit belief construction and validation, but the higher token cost translates into substantially better long-horizon performance.
Who it's for and tradeoffs
Great fit if you build LLM agents that must operate over many steps in partially observable environments or perform evidence-seeking diagnosis and need an interpretable decision state and automated recovery when progress stalls. Look elsewhere if inference token budget is extremely constrained or if a lightweight history-compression strategy is preferable over continual belief maintenance.
Where it fits
PoS sits between naive history retention and full RL-style policy learning: it treats belief construction as the decision context (a posterior over latent world state plus explicit unresolved requirements) and invests inference-time computation in validating and repairing that belief. This makes it complementary to memory-compression or purely replay-based approaches.
How it works (high level)
- Belief Modeling: Maintain a structured world state (entities, states, relations) and two gap sets—epistemic (unknowns) and achievement (things that still must be done).
- Belief Sentinel: Validate belief updates for internal consistency and evidential support to avoid conflicting or unsupported inferences.
- Trapping detection & recovery: Monitor belief transitions for gap persistence, stagnation, and recurrence; diagnose trapping along agent-dynamics and blocked-gap dimensions; compose recovery constraints that focus subsequent action selection on unblockable gaps or informative evidence acquisition.