PABU: Progress-Aware Belief Update for Efficient LLM Agents

Jiang, Haitao; Ge, Lin; Cai, Hengrui; Song, Rui

PABU: Progress-Aware Belief Update for Efficient LLM Agents

Haitao Jiang, Lin Ge, Hengrui Cai, Rui Song

North Carolina State University
A Preprint

Paper Code

Model

Data

Abstract

Large Language Model (LLM) agents commonly condition actions on full action--observation histories, which introduce task-irrelevant information that easily leads to redundant actions and higher inference cost. We propose Progress-Aware Belief Update (PABU), a belief-state framework that compactly represents an agent's state by explicitly modeling task progress and selectively retaining past actions and observations. At each step, the agent predicts its relative progress since the previous round and decides whether the newly encountered interaction should be stored, conditioning future decisions only on the retained subset. Across eight environments in the AgentGym benchmark, and using identical training trajectories, PABU achieves an 81.0% task completion rate, outperforming previous State of the art (SoTA) models with full-history belief by 23.9%. Additionally, PABU's progress-oriented action selection improves efficiency, reducing the average number of interaction steps to 9.5, corresponding to a 26.9% reduction. Ablation studies show that both explicit progress prediction and selective retention are necessary for robust belief learning and performance gains.

Methodologies

Motivation for Progress-aware Belief Update.

In a task such as heating and drinking milk, conventional methods rely on full interaction histories (left), which are noisy, redundant, and expensive to process. Our method (right) performs progress-aware belief updates, preserving only essential information and yielding a compact context that supports efficient and reliable learning.

Experiments

Main Result: Evaluating task completion and efficiency on the AgentGym suite.

For each method, we report the task completion rate (↑ succ %, higher is better) and the number of interaction steps (↓ step #, lower is better). Aggregated performance across eight tasks is summarized in the ∑ column, and the best-performing model is highlighted in bold.

Ablation Analysis 1: Performance comparison across different backbone models.

Smaller models can learn embodied environments effectively given sufficient training samples, while larger models generally perform better in environments that require deeper language understanding.

Ablation Analysis 2: Effect of context ablations on efficiency and performance.

Each point shows the interaction steps and task completion rate after removing a context component. Retaining observation history is critical for tasks that require long-term referencing of multiple observations, action history is most important in environments where similar observations may require diverse responses, while removing available actions disproportionately degrades performance in environments with evolving action spaces. These results illustrate how task structure shapes optimal context-selection strategies.

Ablation Analysis 3: Attribution Analysis across Training Procedures.

Progress-based action filtering (ORM→PRM) and augmentation (PRM→progress-based action augmentation) consistently improve performance under history-based belief representations. Incorporating PABU further refines belief design and yields additional gains beyond next decision filtering and augmentation alone.

BibTeX

@misc{jiang2026pabuprogressawarebeliefupdate,
      title={PABU: Progress-Aware Belief Update for Efficient LLM Agents}, 
      author={Haitao Jiang and Lin Ge and Hengrui Cai and Rui Song},
      year={2026},
      eprint={2602.09138},
      archivePrefix={arXiv},
      primaryClass={cs.AI},
      url={https://arxiv.org/abs/2602.09138}, 
}

PABU: Progress-Aware Belief Update for Efficient LLM Agents

Abstract

Methodologies

Experiments

Ablation Analysis 1: Performance comparison across different backbone models. Smaller models can learn embodied environments effectively given sufficient training samples, while larger models generally perform better in environments that require deeper language understanding.

BibTeX

Ablation Analysis 1: Performance comparison across different backbone models.

Smaller models can learn embodied environments effectively given sufficient training samples, while larger models generally perform better in environments that require deeper language understanding.