Beyond Memory: Harnessing Long-Horizon Agents with Explicit Belief States
Yu Luo, Jiamin Jiang, Yimin Zuo, Xidao Wen, Rongchen Gao, Yongqian Sun, Shenglin Zhang, Guiyang Liu and 4 others
Nankai University · Alibaba Group · Tsinghua University
Published October 1, 2026 · on the feed October 2, 2026 · ▲ 86 · arXiv 2610.01415
The abstract
Large language model (LLM) agents can now undertake increasingly complex tasks, but the way they organize interaction history into memory does not ensure a coherent understanding of the current world. We introduce PoS, an inference-time framework that constructs and continually maintains explicit belief states as the agent's decision context. Each belief combines an estimate of the current world state with unresolved task requirements, making explicit what the agent still needs to learn and accomplish. To keep this belief reliable and actionable, PoS validates its consistency and monitors task progress to detect Belief Trapping, where the agent continues to act without making meaningful progress toward the goal. Recovery is then tailored to both the trapping pattern and the type of unresolved task requirement. Experiments on four benchmarks spanning execution and diagnosis show that PoS achieves the highest overall performance on every benchmark with all three LLM backbones. Ablations demonstrate the importance of consistency validation and recovery, while context-scaling experiments show resilience to context growth. Together, these results support belief construction and continual maintenance as a foundation for long-horizon context management beyond history retention and compression.
The Brief
2:21A short podcast summary of the paper. Written and voiced by AI.
Transcript
Beyond Memory. Harnessing Long-Horizon Agents with Explicit Belief States. By Yu Luo and eleven others, from Nankai University, Alibaba Group, and one other institution. Published on the first of October. Its code repository is worked out: about three hundred and fifty source files, with a readme and a licence.
Large language model agents can now take on increasingly complex tasks. The trouble lies in how they organise interaction history into memory. However it is retained or compressed, a record of what happened does not ensure a coherent understanding of the world as it currently is. An agent can hold a long history and still not know what is true now, or what is left to do.
PoS replaces history as the decision context with something more explicit. It is an inference-time framework that constructs, and continually maintains, explicit belief states, and the agent decides from those. Each belief combines two parts. One is an estimate of the current world state. The other is the set of task requirements still unresolved. Put together, they make explicit what the agent still needs to learn, and what it still needs to accomplish. The contrast with memory is in the tense. A history is a record of the past. A belief is a claim about the present, paired with a list of what is still open, and it is revised as the interaction goes on.
A belief is only useful if it is reliable and actionable, and PoS keeps it that way in two ways. It validates the belief's consistency. And it monitors task progress, to detect a condition the authors name Belief Trapping: the agent keeps acting without making meaningful progress toward the goal. Once trapping is detected, recovery is tailored to two things, the pattern the trapping takes, and the type of task requirement that is still unresolved.
Experiments cover four benchmarks, spanning execution and diagnosis, with three LLM backbones. PoS achieves the highest overall performance on every benchmark, with all three backbones. Ablations show that consistency validation and recovery both matter. Context-scaling experiments show resilience as the context grows, which is the condition long-horizon tasks create by their nature.
Memory answers the question of what has happened. A belief state answers a different one: what is the case, and what remains. The authors read their results as support for building and continually maintaining that second answer as the foundation of long-horizon context management, going beyond retaining or compressing history.
Paper Quest · 7 chapters · about 40 min
Play this paper
Learn it by doing: make the calls the authors made, guess the result before you see it, and defend it in a viva graded on your own words. Chapter 1 is right here.
Chapter 1 🧩 · The problem
Long tasks bury agents in their own history. Here is where it bites.
You run a language-model agent on long household and diagnosis tasks. Its history keeps growing, and actions change the world, so earlier observations quietly go out of date.
The road ahead
- 1 · The problem ~6 min On long tasks an agent's growing history goes stale, and keeping or shrinking it does not tell the agent what is true now.
- 2 · What came before ~3 min
- 3 · The key idea ~9 min The agent decides from an explicit belief about the present, checks each update, and recovers in a targeted way when it stops making progress.
- 4 · Choose your own research ~3 min
- 5 · Build the method ~8 min PoS builds a belief, acts from it, checks each update, watches for stalls, and recovers with constraints fitted to the stall.
- 6 · The experiment ~6 min You’ll guess: Across four agent benchmarks and three LLM backbones, how did PoS rank in overall performance?
- 7 · The viva ~5 min Three questions from the examiners, answered in your own words. Win it for the paper’s trophy.
Free, with Google or an email address. Your stars and progress are kept.