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, Cheng Zhang, Fang Situ, Qi Zhou, Dan Pei
PoS maintains an explicit, validated belief state to prevent long-horizon agents from stalling in unproductive cycles.
How can LLM agents maintain a coherent world model over long horizons to avoid "belief trapping," where they get stuck in incorrect assumptions about the environment?
Long-horizon agents often fail because they rely on raw interaction history, which mixes outdated facts with current evidence and makes it impossible to track what remains to be done. Progression of States (PoS) replaces this passive history with an explicit, task-conditioned belief state that tracks world entities, relations, and unresolved gaps, while using a "Belief Sentinel" to validate updates and detect when the agent is trapped in unproductive cycles. PoS achieves the highest performance across four benchmarks, with relative gains of up to 37.89% on diagnostic tasks and 22.68% on execution tasks compared to the strongest baselines.
Paper Primer
The core mechanism is a three-part loop: Belief Modeling constructs a structured state of entities and gaps; the Belief Sentinel audits every update for internal and external consistency; and Trapping-Aware Recovery diagnoses stalled progress to force the agent out of repetitive or drifting behaviors. The system is like a navigator who keeps a live map of the terrain and their remaining checklist, constantly checking their current position against the map to ensure they aren't walking in circles.
PoS consistently outperforms raw history and existing context-management baselines across both execution and diagnosis tasks.
Relative gains over the strongest baseline reached 22.68% on ALFWorld and 37.89% on RCA-100 joint accuracy. Highest overall performance on all four benchmarks with all three LLM backbones.
Consistency validation and trapping recovery are both essential for performance.
Removing consistency validation caused performance drops of up to 14.93 points, while removing trapping recovery led to losses of up to 6.79 points. Ablations confirm that explicit belief construction alone is insufficient without active maintenance.
Why is "raw history" insufficient for long-horizon tasks?
Raw trajectories preserve chronological evidence but do not provide a coherent, revisable estimate of the current world, causing agents to struggle with conflicting information and outdated inferences as the context grows.
What is "Belief Trapping" and how does PoS fix it?
Belief Trapping occurs when an agent continues to act without making meaningful progress, such as cycling through states or drifting. PoS detects this by measuring gap persistence and belief recurrence, then applies factorized recovery constraints to redirect the agent's actions.
The Problem of Belief Trapping
LLM agents falter on long‑horizon tasks because implicit memory yields persistent, incorrect world models.
LLM agents now handle ever‑more complex, long‑horizon tasks, yet their reliance on implicit memory means they cannot guarantee a coherent, up‑to‑date picture of the world, leading to persistent, incorrect models that stall progress.
When an agent’s internal model of the environment becomes stale or contradictory, it keeps acting on that wrong model, repeating ineffective actions and never advancing toward the goal.
**Figure 1.** **Performance and motivation of PoS.** Left: PoS outperforms the strongest baseline for each backbone across four benchmarks. Right: a real ALFWorld case contrasts implicit belief reconstruction that leads to *Belief Trapping* with explicit belief maintenance in PoS, which enables consistency validation and recovery toward task completion.
We therefore propose Persistent State (PoS), an inference‑time framework that builds an explicit belief, validates its consistency, and applies trapping‑aware recovery to keep long‑horizon agents on track.
Implicit memory fails in long‑horizon tasks because it cannot guarantee that the agent’s current world model stays consistent with new evidence.
The PoS Framework
PoS maintains an explicit, task-conditioned belief state and uses a sentinel-based validation loop to recover from trapping.
PoS addresses the limitations of implicit memory by explicitly modeling the agent's world state and task requirements. It operates through three integrated modules: Belief Modeling, Belief-Guided Interaction, and Trapping-Aware Recovery.
PoS maintains an explicit decision context $B_t$ that separates the agent's current understanding of the world from the specific gaps it must resolve to complete the task.
To prevent the agent from oscillating between tasks, PoS selects a single active gap $\Delta_t$ as the focus for action selection, while the Belief Sentinel validates updates to prevent hallucinated beliefs from persisting.
PoS detects trapping by monitoring belief health $H_t$ over a sliding window, then diagnoses the specific trapping pattern to apply targeted recovery constraints.
**Figure 2.** Overview of PoS. Belief Modeling constructs and incrementally updates a task-conditioned Belief from interaction evidence (Section 3.1). Belief-Guided Interaction conditions each action on the current Belief and an Active Gap, while the Belief Sentinel validates consistency and records task-relevant progress (Section 3.2). Trapping-Aware Recovery estimates Belief health, diagnoses heterogeneous trapping conditions, and composes recovery constraints to restore progress (Section 3.3).
Empirical Evaluation
PoS beats all baselines on every benchmark, delivering the largest gain of 37.89 % on RCA‑100.
PoS consistently outperforms all baselines across every benchmark and backbone, achieving the largest relative gain of 37.89 % on RCA‑100 joint accuracy.
Table 1 shows PoS attaining the highest joint accuracy on RCA‑100 for each of the three backbones, surpassing the next‑best method by up to 37.89 %.
Goal‑directed task execution where an agent must repeatedly act to bring the environment into a target state.
A long‑context decision‑making benchmark where the agent must succeed as the available context grows from 8 K to 256 K tokens.
An evidence‑seeking diagnosis task where the agent gathers discriminative observations to select the correct hypothesis among 100 candidates.
A clinical diagnosis benchmark where the agent interacts with a simulated patient to collect evidence and output a diagnosis.
PoS consistently outperforms trajectory‑based baselines across diverse long‑horizon tasks.
Workflow and Implementation
Describes the PoS inference loop, trapping detection, and design rationale.
This section details the PoS inference loop, how belief trapping is detected and recovered, and the rationale behind the chosen health signals.
Initialize belief and active gap: $(B_{0}, \Delta_{0}) \leftarrow \text{InitializeBelief}(G, o_{0})$.
Set constraint set $C_{0} \leftarrow \emptyset$.
For each timestep $t = 0 \dots T\!-\!1$, sample action $a_{t} \sim \pi(\cdot \mid B_{t}, \Delta_{t}, C_{t})$.
Execute $a_{t}$ in the environment to obtain observation $o_{t+1} \leftarrow \text{EnvironmentStep}(a_{t})$.
Update belief $B_{t+1} \leftarrow U(B_{t}, a_{t}, o_{t+1})$ and run the belief sentinel to enforce consistency.
If the task is diagnostic, compute diagnostic label $d_{\text{diag},t+1}$ and update progress $u_{t+1}$.
If $o_{t+1}$ is terminal, return the environment result.
Advance the active gap $\Delta_{t+1} \leftarrow \text{AdvanceActiveGap}(B_{t+1}, \Delta_{t})$.
When $t\!+\!1 \ge K$, form the sliding window $W_{t+1}$, compute persistence $P_{E},P_{A}$, stagnation $S_{t+1}$, and recurrence $R_{t+1}$, and evaluate health $H_{t+1}$.
If $H_{t+1} \le \theta_{H}$, classify dynamics, select a blocked‑gap type, and compose constraints $C_{t+1}$.
PoS watches a health score; when it falls below a threshold, the system diagnoses a trapping pattern and injects constraints that steer the next action while keeping the active gap unchanged.
How does this detection differ from a simple confidence‑threshold check?
A plain threshold looks only at the magnitude of confidence changes, ignoring whether the same requirement remains unresolved (persistence) or whether beliefs recur. PoS combines all three signals, so a trap is flagged only when an unresolved requirement coincides with either stagnation or recurrence, reducing spurious alerts.
The three health signals were chosen because each captures a distinct failure mode: Persistence ties the score to unresolved requirements, Stagnation flags lack of progress, and Recurrence catches repeated belief configurations that may hide hidden loops.
**Table 4.** Health scores under three illustrative boundary configurations. Lower values indicate stronger trapping signals.
Benchmark Taxonomy
Provides a taxonomy of benchmarks, dataset splits, interaction protocols, and evaluation metrics.
Embodied manipulation benchmark with three task types: Place, Transform, and Inspect.
Multi‑domain benchmark organized into three task categories.
Diagnostic benchmark with three evaluation targets.
Clinical diagnosis benchmark split into common and rare case subsets.
**Table 5.** Dataset statistics and evaluation splits.
Ablation and Diagnostic Analysis
Fine-grained ablations reveal how each PoS component drives performance gains.
LLM agents get stuck in belief traps; PoS mitigates this by maintaining explicit beliefs.
PoS raises ALFWorld success from 56.00 % to 81.33 % with Qwen3.7‑Plus, a +25.33 % improvement.
Table 9 reports the increase.
Qualitative Case Study
A concrete RCA‑100 case shows PoS diagnosing and recovering from belief trapping.
PoS resolves the belief trap in the RCA‑100 t024 case within five steps, delivering the correct diagnosis at step 27.
The trace shows belief revision at step 26 and successful submission at step 27 after a targeted CPU investigation.
The agent begins with an unresolved diagnostic question, believing slow inventory requests stem from garbage‑collection activity while an epistemic gap remains between database waiting and JVM‑side processing. At step 22 PoS flags a static stagnation pattern, enforcing constraints to avoid repeating ineffective actions and to seek distinguishing evidence.
Guided by these constraints, the agent inspects CPU activity, gathers new evidence, and integrates it with prior GC observations, shifting belief support toward JVM‑side processing. By step 26 the epistemic gap is resolved, and at step 27 the agent submits the correct failure type, demonstrating targeted recovery.
Notation and Formalism
This section defines the symbols used throughout the PoS framework.
This section compiles the symbolic vocabulary that the PoS framework relies on.
Notation provides a compact vocabulary for the PoS framework, letting us refer precisely to states, actions, beliefs, and diagnostic quantities.
**Table 3.** Summary of the principal notation used in PoS.
Reproducibility and Configuration
Implementation specifics for backbones, baselines, and PoS hyperparameters.
All experiments share a common implementation pipeline. We keep the evaluation protocol identical across backbones and baselines to isolate the effect of the PoS framework.
We evaluate three backbones—Qwen3.7‑Plus, Kimi‑K3, and GLM‑5.3—via the DashScope OpenAI‑compatible API. For each backbone, every LLM‑based component of PoS and the baselines uses the same model; no auxiliary model is introduced for belief construction or recovery.
Baseline selection covers representative decision‑context strategies. Raw Trajectory exposes the full interaction history, while ACON, PACE, and HiAgent provide compressed, adaptive, and hierarchical memory respectively. LongHorizon‑Harness adds an explicit audited task‑state mechanism.
All baselines are integrated through a shared ReAct harness, except LongHorizon‑Harness which retains its native Manage‑Execute‑Audit workflow. We preserve each method’s core context‑management mechanism while adapting its interaction layer to the common benchmark interfaces.
PoS hyperparameters are listed in Table 8. Belief updates and local audits occur every step; global audits run every 32 steps on LOCA‑Bench and every 8 steps on the other benchmarks. Thresholds such as $\epsilon_W\!=\!0.15$, $\epsilon\!=\!0.30$, $\theta_H\!=\!0.25$, and $\theta_R\!=\!0.75$ govern detection, diagnostic progress, health, and cycle recurrence.
**Table 7.** Decision contexts and implementation provenance of the evaluated baselines. All methods share the same benchmark interface and environment-action budget. The main differences lie in how interaction evidence is represented and exposed for subsequent decision making.
**Table 8.** Hyperparameter configuration of PoS. Intervals are measured in interaction steps.