Beyond Memory: Harnessing Long-Horizon Agents with Explicit Belief States

AI summary

Overview

• Research area: Long-horizon LLM agent context management, POMDP-based belief state modeling, and agent failure-mode diagnosis and recovery.
• Technical level: Intermediate (requires familiarity with LLM agents, memory/context management, and the notion of a belief state from POMDPs, but the core argument is accessible).
• Scope: The paper introduces PoS (Progression of States), an inference-time framework that builds and continually maintains an explicit belief state — a world state plus unresolved task gaps — and validates, diagnoses, and recovers from a failure mode the authors call Belief Trapping, evaluated on four benchmarks with three LLM backbones.

What This Paper Is About

LLM agents typically carry their interaction history forward either as a raw chronological trajectory or as some compressed, summarized, or reorganized memory. The authors argue that access to evidence is not the same as having a coherent, current estimate of the world: outdated or conflicting inferences can persist across steps, and agents can keep acting productively-looking while never advancing the goal. The paper's goal is to maintain an explicit, task-conditioned belief state as the decision context, to validate it against evidence, and to detect and recover from stalled progress during the episode rather than merely truncating or terminating it.

Key Contributions

1. A task-conditioned belief representation. PoS maintains a belief B_t = (W_t, G, Δ_t^E, Δ_t^A), where W_t is a task-relevant world state structured as Entities, States, and Relations (with provenance, confidence, and supporting evidence), G is the task goal, and the two gap sets separate what the agent still needs to learn (epistemic) from what it still needs to accomplish (achievement).
2. A Belief Sentinel for consistency validation. Candidate belief updates produced by the task agent are treated as unverified (B̃_{t+1}) and audited for internal inconsistency (mutually conflicting content) and external inconsistency (contradiction with the latest observation or other interaction evidence) before being committed as B_{t+1}.
3. Belief Trapping: diagnosis and factorized recovery. The paper defines and operationalizes Belief Trapping — continuing to act without meaningful progress — and estimates belief health from three window-level signals (gap persistence, progress stagnation, belief recurrence). Trapping is diagnosed along two dimensions (agent dynamics: Static, Cycle, or Drift; and blocked gap type: epistemic or achievement) and recovery constraints are composed per diagnosis.
4. Empirical validation across execution and diagnosis. Evaluated on four benchmarks (ALFWorld, LOCA-Bench, RCA-100, ClinDiag) with three backbones (Qwen3.7-Plus, Kimi-K3, GLM-5.3), with ablations isolating consistency validation and trapping recovery, plus context-scaling and cost analyses.

Main Findings

• PoS attains the highest overall performance on all four benchmarks under all three backbones. Relative gains over the strongest baseline with the same backbone reach 22.68% on ALFWorld, 7.53% on LOCA-Bench, 37.89% on RCA-100 joint accuracy, and 11.31% on ClinDiag.
• Existing context management does not consistently beat raw trajectories. PACE falls 24.57–28.19 points below Raw Trajectory on LOCA-Bench; LongHorizon-Harness performs well on LOCA-Bench but delivers less consistent gains on RCA-100 and ClinDiag; on ClinDiag with GLM-5.3, none of the context-management baselines outperforms Raw Trajectory. The authors attribute these reversals to information loss offsetting the benefit of reducing redundancy for strong long-context models.
• Consistency validation is the larger ablation effect. Removing it lowers performance across all four benchmarks, with losses reaching 14.93 points on ALFWorld and 11.81 points on LOCA-Bench, versus only 0.33–0.66 points on ClinDiag.
• Trapping diagnosis and recovery also contribute broadly. Removing them degrades all four benchmarks, including 4.85–6.79 points on RCA-100 and 2.65–3.97 points on ClinDiag.
• Trapping is common, and a stronger backbone is not always the least-trapped. On RCA-100, Kimi-K3 shows more trapping than GLM-5.3 (74% vs. 53%) yet achieves higher joint accuracy. The dominant pattern varies by benchmark: cycles most frequent in ALFWorld, drift in LOCA-Bench and RCA-100 (55.93%), and static stagnation in ClinDiag (78.25%).
• Factorized recovery beats a generic recovery prompt. Replacing PoS's factorized recovery constraints with a generic prompt asking the agent to recover underperforms PoS across all four benchmarks (Qwen3.7-Plus, all evaluated cases).
• Cost increases, but task-agent tokens decrease. On RCA-100 with Qwen3.7-Plus (averaged over all 103 cases), PoS raises joint accuracy from 24.27% to 38.83% while cutting Task Agent token consumption by 20.9%; total consumption rises to 5.06×. Removing consistency validation saves 35.6% of total tokens but costs 7.76 joint-accuracy points; removing trapping diagnosis saves only 9.2% of total tokens while reducing joint accuracy by 4.85 points.
• Resilience to context growth. On LOCA-Bench, as environment descriptions grow from 8K to 256K, PoS stays broadly stable from 96K to 256K, exceeding the strongest baseline by 10.67–16.00 points at 256K. ACON declines more gradually than Raw Trajectory at longer contexts.

Methodology in Plain English

The interaction is framed as a POMDP: the environment has a latent state the agent cannot see directly, so the agent should act on a belief — its posterior over the current world given history. PoS materializes that belief as an explicit, structured object rather than letting it stay implicit in a growing context.

The belief has four parts: a world state listing the Entities, States, and Relations that matter for the task (each with provenance, confidence, and evidence when available); the goal; and two gap sets tracking unresolved information and unresolved goal conditions. From these, PoS picks one active gap to focus on, so the agent is not spread across many simultaneously. Actions are chosen conditioned on the full belief, the active gap, and any recovery constraint (which is empty during normal operation).

After each action and observation, the task agent proposes a candidate belief update. Because that proposal comes from the same LLM, it can carry hallucinations or conflicting content, so a Belief Sentinel audits it and returns issues for the agent to resolve against evidence before the update is committed.

Progress is then scored. Each validated transition gets a binary progress label: for diagnosis tasks, from the total-variation change in confidence distributions over inferred States and Relations (using a threshold to filter minor fluctuations); for execution tasks, from the Sentinel's judgment of whether the transition reduced the active gap, gathered needed information, or advanced a plausible path. Over a window of the K most recent validated transitions, PoS computes gap persistence (fraction of initially unresolved gaps of each type still unresolved), progress stagnation (fraction of transitions without progress), and belief recurrence (how often the active-gap-relevant world state repeats, taking the strongest recurrence rate across candidate lags, measured with Jaccard distance over Entity, State, and Relation sets). Belief health is H_t = 1 − max_X [P_X · max(S_t, R_t)], and trapping is declared when health drops to or below a threshold.

Detection triggers diagnosis: agent dynamics are classified as Static (world state locally unchanged), Cycle (periodic recurrence with dominant lag greater than one), or Drift (world changes that do not advance the active-gap projection), and the blocked gap type is whichever of epistemic or achievement has higher persistence. Recovery then composes a pattern-specific escape constraint (suppress the ineffective transition, break the recurrent transition, or re-anchor to the active gap) with a gap-specific progress constraint (require new discriminative evidence for epistemic gaps, a task-relevant state change for achievement gaps). Recovery is released once health rises above the threshold; otherwise the diagnosis and constraints are updated. All evaluations use deterministic decoding at temperature 0, and within each backbone setting all LLM components use the same backbone.

Why This Matters

• Impact on research: The paper reframes long-horizon context management as belief maintenance rather than history retention or compression, and it contributes a concrete failure taxonomy (Belief Trapping, with Static/Cycle/Drift dynamics and blocked epistemic vs. achievement gaps) plus a diagnosis-and-recovery procedure. It also reports evidence that prior context-management methods — including explicitly structured ones such as LongHorizon-Harness, which depends on independently verifiable intermediate results — do not consistently improve on raw trajectories, which is methodologically informative for future benchmarking.
• Real-world applications:
  • Embodied or household assistants that must track object states (open/closed, held, dirty) over many actions, as tested on ALFWorld.
  • IT operations and cloud incident root-cause analysis, where the agent gathers evidence across sources and must converge on a diagnosis (RCA-100).
  • Clinical decision support, where investigations may be non-discriminative and diagnostic belief can stall (ClinDiag).
  • Long-context enterprise agents handling many-tool workflows where environment descriptions are large and errors compound silently.
• Industry relevance: The framework directly addresses the practical failure of agents burning budget on unproductive loops, and the paper reports the explicit cost tradeoff — higher total token use versus fewer tokens consumed by the task agent itself — which is the kind of accounting deployment teams need when deciding where to spend inference-time compute.

Future Directions

• Reducing overhead while preserving gains. The authors explicitly name this as an important direction, since total consumption on RCA-100 rose to 5.06× that of Raw Trajectory.
• Extending beyond independently verifiable progress. The paper notes that LongHorizon-Harness is less suitable when meaningful progress consists of uncertain inferences rather than observable outcomes — the same tension applies to validating achievement gaps in open-ended domains.
• Generalizing the trapping taxonomy. The dominant pattern was benchmark-specific (cycles in ALFWorld, drift in LOCA-Bench and RCA-100, static stagnation in ClinDiag), leaving open whether additional dynamics patterns or gap types are needed in other domains.
• Understanding the relationship between trapping incidence and accuracy. Lower trapping incidence did not imply higher final accuracy (Kimi-K3 vs. GLM-5.3 on RCA-100), which raises the question of how backbone capability, detection thresholds, and task structure interact.

Target Audience

Researchers and engineers working on LLM agents, long-horizon planning, and context/memory management; practitioners deploying multi-step agents in embodied, IT operations, or diagnostic settings; and readers interested in applying POMDP belief-state ideas to LLM inference-time control. Some background in LLM agent architectures and agent failure modes is helpful, but the diagnosis-and-recovery mechanics are presented concretely enough to be followed without a POMDP specialization. Paper code and project page are linked in the paper.

Authors’ 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.