Skip to content

Back to the catalog

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

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

This paper introduces PoS, an inference-time framework for LLM agents that maintains explicit belief states — combining an estimate of the current world state with unresolved task requirements — instead of relying solely on raw interaction history or memory compression. PoS detects "Belief Trapping," where an agent keeps acting without real progress, and applies recovery strategies tailored to the trapping pattern and the unresolved requirement type. Across four benchmarks spanning execution and diagnosis tasks, and three different LLM backbones, PoS outperforms baseline approaches and shows resilience as context length grows.

TL;DR A new framework (PoS) gives long-horizon LLM agents explicit, continually-validated belief states instead of just memory, improving performance and context resilience across benchmarks.
Open original ↗
Document

What it claims

PoS ("Progression of States") is an inference-time wrapper for LLM agents. Instead of acting on a raw trajectory or a compressed memory, the agent acts on a structured belief that the framework validates and checks for progress at every step. It is evaluated on ALFWorld and LOCA-Bench (execution tasks) and RCA-100 and ClinDiag (diagnosis tasks) with three LLM backbones. The paper reports the highest overall score on all four benchmarks with every backbone. Relative gains over the strongest baseline reach 22.68% on ALFWorld and 37.89% on RCA-100 joint accuracy. In the paper's ALFWorld case #0096, a baseline agent runs "examine cabinet" 36 times and fails after 50 steps; PoS finishes the same task in 17 steps.

How it works

The belief is B_t = (W_t, G, Δ^E_t, Δ^A_t):

  • W_t, the world state. It is a graph of Entities, natural-language States and directed Relations. Each State and Relation carries provenance, a confidence value and evidence. The graph keeps only records that affect whether an action is feasible or whether the goal is met.
  • Δ^E, epistemic gaps. These are facts the agent still needs to learn.
  • Δ^A, achievement gaps. These are differences from the goal state that the agent must close by acting.

Each step runs as follows:

  1. The agent picks one active gap and selects an action conditioned on the belief, the active gap and any recovery constraint.
  2. The agent proposes a candidate belief update.
  3. A separate Belief Sentinel audits the changed records. It checks for internal conflicts, such as a microwave recorded as both open and closed, and for external conflicts with the trajectory evidence. It sends any issues back to the agent, which revises the update before committing it.
  4. The framework gives each validated transition a 0/1 progress label. For diagnosis tasks, the label is 1 when the total confidence change exceeds a threshold ε.

Three signals of belief health detect Belief Trapping: gap persistence, progress stagnation and belief recurrence. Diagnosis is factorized along two axes:

  • Trapping pattern: static, cycle or drift.
  • Blocked gap type: epistemic or achievement.

Recovery constraints from the two axes are combined:

  • Pattern constraints: suppress the ineffective action, cut the recurrent edge, or re-anchor to the active gap.
  • Gap constraints: acquire discriminative evidence, or induce a goal-relevant state change.

The constraint is released once progress resumes.

flowchart TD
    A[Act on belief + active gap] --> U[Candidate belief update]
    U --> S{Sentinel: consistent?}
    S -- issues --> U
    S -- ok --> H{Health: trapped?}
    H -- no --> A
    H -- yes --> D[Diagnose pattern × gap type]
    D --> C[Compose recovery constraint]
    C --> A2[Constrained action]
    A2 --> R{Progress restored?}
    R -- yes --> A
    R -- no --> D

The paper positions PoS against two related methods:

  • T³: truncates stalled trajectories during RL training.
  • LongHorizon-Harness: needs intermediate results that can be verified independently.

The paper argues that PoS recovers inside the episode, and that it also works when progress consists of uncertain inferences rather than observable outcomes.

Evidence

The fetched text gives only relative gains, not absolute scores or baseline names per benchmark. Baselines compared include ReAct-style raw trajectories and memory/compression methods. Ablations show that consistency validation and trapping recovery both contribute beyond building the belief alone. Context-scaling experiments show resilience as context grows. The paper also analyses token consumption against performance, but the fetched text stops before those figures.

How to use it

No install commands, licence or backbone names appear in the fetched text.

Limits

  • Truncated page. The text ends partway through Section 3.3. It omits:
  • how execution tasks get progress labels
  • the results tables
  • the three backbones
  • the token-cost numbers
  • Added cost. Each step adds a Sentinel validation call and a revision step. Check the token-cost analysis before adopting.
  • Hand-set threshold. The progress threshold ε is predefined, not learned.
  • Relative headline numbers. The 22.68% and 37.89% are relative gains over the strongest per-backbone baseline. Read the absolute numbers in the paper.

Technologies named here

Techniques named here

  • Explicit belief states
  • Belief Trapping detection and recovery

Related in agents