PoS: Breaking Belief Trapping in Long-Horizon Agents with Explicit Belief States

Problem: Belief Trapping in Long-Horizon Agents

In a simulated ALFWorld task, an agent must heat a cup and place it in a cabinet. The agent puts the cup in the microwave, then the cabinet, but then repeatedly checks the cabinet 36 times until its action budget is exhausted, never completing the heating step. A raw trajectory baseline using full interaction history fails after 50 steps, while PoS completes the task in 17 steps. This illustrates Belief Trapping : the agent continues interacting with the environment, but its goal-relevant belief evolution no longer yields meaningful task progress. Trapping can manifest as exact repetition, cycling among states, or exploring without addressing the true unresolved requirement.

PoS Framework: Explicit Belief States and Belief Health

PoS (Progression of States) continuously maintains an explicit belief state that records the current world and unresolved requirements. It measures task progression with Belief Health , detects trapping, and applies Trapping-Aware Recovery based on the trapping pattern and gap type. This forms a closed loop from detection to recovery.

Belief State Representation

PoS organizes task-relevant world information using entities, states, and relations (e.g., cup, microwave, cabinet; cup is hot, microwave is closed; cup located in microwave). Each state and relation retains provenance, confidence, and supporting evidence. Only information affecting actions, outcome judgment, or goal completion is kept. Unresolved requirements are split into Epistemic Gaps (need more information) and Achievement Gaps (need state change via action). An Active Gap is selected for focused action while the full task state remains visible.

Belief Sentinel: Consistency Verification

After each action returns a new observation, PoS generates a candidate belief update and passes it to the Belief Sentinel . The Sentinel checks internal consistency (e.g., a microwave cannot be both open and closed) and whether updates are supported by interaction evidence (e.g., placing a cup in a microwave does not prove it is heated). Only verified updates enter subsequent decision-making. If verification fails, the previous committed state is retained.

Belief Health: Quantifying Progress Stagnation

Belief Health (Hₜ) is a heuristic metric computed over the last K verified state transitions. It combines three signals: (1) single-step progress (gap reduction, information gain, or advancement along a plausible completion path), (2) confidence change in relevant inferences (including decreases that rule out wrong explanations), and (3) persistence of unresolved gaps. The formula uses inner max to preserve the stronger anomaly between stagnation and repetition, multiplies by gap persistence, and takes outer max across gap types. Trapping detection triggers after 8 verified transitions when Hₜ ≤ 0.25.

Trapping-Aware Recovery: Pattern and Gap Constraints

Recovery diagnoses two dimensions: behavior pattern (Static — local world state unchanged; Cycle — periodic revisiting of prior states; Drift — world changes but gap-relevant parts do not advance) and blocked gap type (epistemic vs. achievement). Constraints are generated to break the specific pattern (suppress invalid state-action repeats, break cycles, realign Active Gap) and to demand discriminative evidence or goal-relevant state change. Constraints are fed as additional conditions to the original agent; Active Gap stays fixed. After each new verified transition, health is recomputed: if above threshold, constraints are released; otherwise diagnosis and constraints are updated.

Experimental Evaluation

PoS is evaluated on four benchmarks: ALFWorld (134 tasks), LOCA-Bench (525 tasks, seven environment lengths), RCA-100 (103 fault diagnosis cases), and ClinDiag (604 medical diagnosis cases). Three base models are used: Qwen3.7-Plus, Kimi-K3, GLM-5.3. PoS components share the same base model; no fine-tuning is required. Compared baselines include Raw Trajectory, ACON, PACE, HiAgent, and LongHorizon-Harness. PoS achieves the highest overall metric in all 12 benchmark×model settings. For Qwen3.7-Plus: ALFWorld success rate rises from 72.39% to 88.81% (+16.42 pp, +22.68% relative); RCA-100 joint accuracy rises from 28.16% to 38.83% (+10.67 pp, +37.89% relative). Improvements cover both "change the world" (ALFWorld, LOCA-Bench) and "accumulate evidence" (RCA-100, ClinDiag) task structures.

Ablation Studies

Removing consistency verification drops ALFWorld from 88.81% to 73.88% and LOCA-Bench from 56.38% to 44.57% (Qwen3.7-Plus), showing reliable state updates are critical for execution tasks. Removing trapping diagnosis and recovery drops RCA-100 joint accuracy from 38.83% to 33.98% (Qwen3.7-Plus), with similar declines across models, confirming recovery redirects actions when investigation stalls. Replacing targeted recovery with a generic "try to recover" prompt yields lower final metrics on all four benchmarks, demonstrating the value of pattern- and gap-specific constraints. Trapping pattern distribution varies by task: ALFWorld shows mostly Cycle; RCA-100 shows 55.93% Drift; ClinDiag shows 78.25% Static.

Long-Context Stability

On LOCA-Bench, environment description length grows from 8K to 256K tokens. All methods degrade, but PoS remains relatively stable in the 96K–256K range. At 256K, PoS outperforms the strongest baseline by 10.67–16.00 percentage points across the three models. This aligns with PoS's design: incremental belief updates reduce the need to repeatedly reconstruct task state from long histories.

Computational Cost

On RCA-100 with Qwen3.7-Plus, PoS raises joint accuracy from 24.27% (raw trajectory) to 38.83%, while total token consumption reaches 5.06× the baseline. The task agent's own token use decreases ~20.9%; extra cost comes from belief maintenance and Sentinel. This reflects a trade-off between higher diagnostic accuracy and additional inference overhead.

Limitations and Future Work

PoS relies on the base model's ability to interpret evidence. Belief Health detects stagnation but does not verify final answer correctness. Even internally consistent, observation-compatible beliefs may contain errors due to domain knowledge gaps. Future directions include more compact latent world-state representations to reduce repeated text generation, and integrating domain knowledge retrieval during state updates to help models interpret specialized evidence.

Open-Source Availability

PoS code is open-sourced at https://github.com/luoyu100/PoS, providing the full framework, raw trajectory baseline, two ablation configurations, and reproduction guides. The project page

https://luoyu100.github.io/projects/progression-of-states/project/

offers interactive demos of progress monitoring, trapping recovery, and execution cases. The paper is available at https://arxiv.org/abs/2610.01415.