Large language model agents are increasingly tasked with complex, long-horizon problems, but the way they organize interaction history into memory does not guarantee a coherent picture of the current world. A new research paper, Beyond Memory: Harnessing Long-Horizon Agents with Explicit Belief States, proposes an inference-time framework called PoS (Progression of States) that builds and continually maintains explicit belief states as the agent's decision context.
Under PoS, each belief pairs an estimate of the current world state with the task requirements that remain unresolved, making explicit what the agent still needs to learn and accomplish. The framework validates belief updates for consistency and evidential support, and monitors whether interactions actually advance the task.
The paper identifies a failure mode it calls Belief Trapping: agents can keep acting without meaningfully progressing toward their goals, even when their maintained belief appears coherent. When progress stalls, PoS diagnoses both the trapping pattern — described as stagnation, cycles, or drift — and the specific blocked requirement, then composes targeted recovery constraints to steer subsequent actions. The approach requires no additional training.
Experiments span four benchmarks covering task execution and evidence-seeking diagnosis, evaluated with three LLM backbones. According to the paper, PoS achieves the highest overall performance in all 12 benchmark–backbone combinations, with relative gains over the strongest same-backbone baseline reaching 22.68% on ALFWorld and 37.89% on RCA-100 joint accuracy.
Ablations highlight the importance of consistency validation and recovery, while context-scaling experiments indicate resilience to context growth. The authors argue these results position belief construction and continual maintenance as a foundation for long-horizon context management that goes beyond history retention and compression.