PoS: Detecting and Escaping Belief Trapping in Long-Horizon AI Agents

The article introduces Belief Trapping : a condition where an agent continues to interact with the environment—calling tools, receiving observations, generating plans—yet its goal-relevant beliefs stop evolving in a way that advances the task. A concrete example from the ALFWorld benchmark shows an agent tasked with placing a heated cup into a cabinet. The agent puts the cup in the microwave, then into the cabinet, but omits the heating step. It then repeats the “look in cabinet” action 36 times until the step budget is exhausted, while the raw-trajectory baseline fails after 50 steps. PoS completes the same task in 17 steps by explicitly tracking the unmet heating requirement.

PoS Architecture

PoS (Progression of States) maintains an explicit belief state that records the current world and unresolved requirements. The belief state uses entities (cup, microwave, cabinet), states (cup heated?, microwave closed?), and relations (cup location, held by) with provenance, confidence, and supporting evidence. Only information that affects actions, outcome judgments, or goal completion is retained.

Unresolved requirements are split into two gap types:

Epistemic Gap : something still to be clarified (e.g., “is the cup hot?”).

Achievement Gap : something still to be changed by action (e.g., “heat the cup”).

An Active Gap is selected for immediate focus 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 (1) internal consistency (e.g., the microwave cannot be both open and closed) and (2) whether the update is supported by interaction evidence (seeing the cup placed in the microwave does not justify writing “cup is heated” as a fact). If the candidate fails, the agent revises it; if it still fails, the previous committed state is retained. This verified state becomes the basis for progress assessment.

Belief Health: Quantifying Trapping

Progress per verified transition is labeled: narrowing the active gap, acquiring necessary information, or advancing a plausible completion path (for execution tasks); or a confidence change exceeding a threshold (for diagnostic tasks). Over the most recent K=8 verified transitions, three complementary signals are computed for each gap type E (epistemic) and A (achievement):

Stagnation : lack of positive progress labels.

Repetition : recurrence of similar belief configurations.

Persistence : duration the gap has remained non-empty.

These are combined into a Belief Health score Hₜ (lower = stronger trapping signal). The formula uses inner max to preserve the stronger of stagnation/repetition, multiplies by persistence to link anomalies to long-standing gaps, and takes an outer max across gap types. When Hₜ ≤ 0.25 after 8 verified transitions, trapping diagnosis is triggered.

Trapping-Aware Recovery

Diagnosis proceeds along two dimensions:

Behavioral pattern (checked in order):

Static : local world state unchanged.

Cycle : cycling through previously seen states.

Drift : world state changes but gap-relevant parts do not advance.

Fallback: generic recovery if no pattern matches.

Blocked gap type : compare persistence of non-empty epistemic vs. achievement gaps; the more stubborn gap dictates whether the agent needs discriminative evidence (epistemic) or a state-changing action (achievement).

The two constraints—pattern constraint (break invalid repetition/cycle/drift) and gap constraint (obtain discriminative evidence or produce goal-relevant state change)—are jointly passed to the base agent as temporary recovery constraints. The Active Gap stays fixed. After each new verified transition, health is recomputed: if Hₜ rises above threshold, constraints are released; otherwise diagnosis and constraints are updated.

Case Study: RCA-100 Fault Diagnosis (t024)

An agent using Kimi-K3 observed that slow requests in the inventory service coincided with elevated GC activity but could not distinguish between database wait and JVM internal processing. PoS diagnosed “Static + Epistemic Gap,” constraining the agent to stop ineffective repetition and seek evidence that discriminates the two explanations. The agent then checked CPU activity; after three low-progress steps, the new CPU evidence combined with existing GC observations revised the belief. The run used 28 actions and the final submission ( inventory / memoryPressure) matched the ground-truth fault entity and type.

Experimental Evaluation

Four benchmarks, three base models (Qwen3.7-Plus, Kimi-K3, GLM-5.3), 12 “benchmark × model” settings:

ALFWorld (134 cases): household task execution.

LOCA-Bench (525 cases, 7 environment-length settings): long-context task execution.

RCA-100 (103 cases): root-cause analysis.

ClinDiag (604 cases): medical diagnosis.

Baselines: Raw Trajectory, ACON, PACE, HiAgent, LongHorizon-Harness. PoS uses the same base model for execution, belief maintenance, and Sentinel—no fine-tuning.

Main Results (Qwen3.7-Plus example)

ALFWorld: 72.39% → 88.81% (+16.42 pp, +22.68% relative).

RCA-100 joint accuracy: 28.16% → 38.83% (+10.67 pp, +37.89% relative).

PoS achieves the highest overall metric in all 12 settings.

Ablation Studies

Removing consistency verification drops ALFWorld to 73.88% and LOCA-Bench to 44.57% (Qwen3.7-Plus), showing reliable state updates are critical for execution tasks.

Removing trapping diagnosis + recovery drops RCA-100 joint accuracy to 33.98% (Δ −4.85 to −6.79 pp across models), showing recovery matters for diagnostic tasks.

Replacing targeted recovery constraints with a generic “try to recover” prompt yields lower final metrics on all four benchmarks, confirming that pattern- and gap-specific constraints are necessary.

Trapping Pattern Distribution

ALFWorld: Cycle dominant.

RCA-100: Drift 55.93%.

ClinDiag: Static 78.25%.

Long-Context Stability (LOCA-Bench)

Environment description scaled from 8K to 256K tokens. All methods degrade, but PoS remains relatively stable in the 96K–256K range, outperforming the strongest baseline by 10.67–16.00 pp at 256K. This aligns with PoS’s design: incremental belief updates reduce the need to repeatedly reconstruct task state from long histories.

Token Overhead

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 execution agent’s own tokens decrease ~20.9%; the extra cost comes from belief construction and Sentinel. This illustrates the trade-off between diagnostic accuracy and inference investment.

Limitations & Future Work

PoS still relies on the base model’s ability to interpret evidence. Belief Health detects stagnation but does not verify final answer correctness; internally consistent, observation-compatible beliefs may still contain domain-knowledge errors. The paper outlines two directions: (1) more compact latent world-state representations to cut repeated text generation, and (2) integrating domain knowledge retrieval into state updates to help models interpret specialized evidence.

Availability

Paper: https://arxiv.org/abs/2610.01415 Project page:

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

Open-source code: https://github.com/luoyu100/PoS (full framework, baselines, ablation configs, reproduction guide, interactive demos).