# PABU: Progress-Aware Belief Update for Efficient LLM Agents

arXiv: https://arxiv.org/abs/2602.09138 · HTML: https://mlsanity.com/paper/2602.09138/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 37 of its 55 references that are in the map.
- First posted on arXiv 9 Feb 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 37)

- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [AgentTuning: Enabling Generalized Agent Abilities for LLMs](https://mlsanity.com/paper/2310.12823/) (2023)
- [ScienceWorld: Is your Agent Smarter than a 5th Grader?](https://mlsanity.com/paper/2203.07540/) (2022)
- [BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning](https://mlsanity.com/paper/1810.08272/) (2018)
- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [ADaPT: As-Needed Decomposition and Planning with Language Models](https://mlsanity.com/paper/2311.05772/) (2023)
- [AutoWebGLM: A Large Language Model-based Web Navigating Agent](https://mlsanity.com/paper/2404.03648/) (2024)
- [AgentGym: Evolving Large Language Model-based Agents across Diverse Environments](https://mlsanity.com/paper/2406.04151/) (2024)
- [xLAM: A Family of Large Action Models to Empower AI Agent Systems](https://mlsanity.com/paper/2409.03215/) (2024)
- [LMRL Gym: Benchmarks for Multi-Turn Reinforcement Learning with Language Models](https://mlsanity.com/paper/2311.18232/) (2023)
- [Watch Every Step! LLM Agent Learning via Iterative Step-Level Process Refinement](https://mlsanity.com/paper/2406.11176/) (2024)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Agent-R: Training Language Model Agents to Reflect via Iterative Self-Training](https://mlsanity.com/paper/2501.11425/) (2025)
- [Direct Multi-Turn Preference Optimization for Language Agents](https://mlsanity.com/paper/2406.14868/) (2024)
- [NNetNav: Unsupervised Learning of Browser Agents Through Environment Interaction in the Wild](https://mlsanity.com/paper/2410.02907/) (2024)
- [AgentBank: Towards Generalized LLM Agents via Fine-Tuning on 50000+ Interaction Trajectories](https://mlsanity.com/paper/2410.07706/) (2024)
- [Offline Reinforcement Learning for LLM Multi-Step Reasoning](https://mlsanity.com/paper/2412.16145/) (2024)
- [AgentOhana: Design Unified Data and Training Pipeline for Effective Agent Learning](https://mlsanity.com/paper/2402.15506/) (2024)
- [AgentRefine: Enhancing Agent Generalization through Refinement Tuning](https://mlsanity.com/paper/2501.01702/) (2025)
- [Scaling LLM Multi-turn RL with End-to-end Summarization-based Context Management](https://mlsanity.com/paper/2510.06727/) (2025)
- [Synatra: Turning Indirect Knowledge into Direct Demonstrations for Digital Agents at Scale](https://mlsanity.com/paper/2409.15637/) (2024)
- [ATLaS: Agent Tuning via Learning Critical Steps](https://mlsanity.com/paper/2503.02197/) (2025)
- [Better than Your Teacher: LLM Agents that learn from Privileged AI Feedback](https://mlsanity.com/paper/2410.05434/) (2024)
- [Countering Reward Over-optimization in LLM with Demonstration-Guided Reinforcement Learning](https://mlsanity.com/paper/2404.19409/) (2024)
- [Adapting LLM Agents with Universal Feedback in Communication](https://mlsanity.com/paper/2310.01444/) (2023)
- [How to Train Your LLM Web Agent: A Statistical Diagnosis](https://mlsanity.com/paper/2507.04103/) (2025)
- [From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven Autonomous Systems](https://mlsanity.com/paper/2405.19883/) (2024)
- [Policy Improvement using Language Feedback Models](https://mlsanity.com/paper/2402.07876/) (2024)

## Built on by (most cited first, 7 of 7)

- [Belief Memory: Agent Memory Under Partial Observability](https://mlsanity.com/paper/2605.05583/) (2026)
- [Agent-BRACE: Decoupling Beliefs from Actions in Long-Horizon Tasks via Verbalized State Uncertainty](https://mlsanity.com/paper/2605.11436/) (2026)
- [Cost-Utility Alignment in LLM Agent Trajectories:Profiling,Attribution,Diagnosis,Adaptation,and Evaluation](https://mlsanity.com/paper/2608.26195/) (2026)
- [Decision-Sufficient State Representations: Measuring and Reducing Write-Time Regret](https://mlsanity.com/paper/2609.32805/) (2026)
- [Intent-Driven Situation Tracking for User-Centric Multi-Turn Agents](https://mlsanity.com/paper/2608.15755/) (2026)
- [CliffCompaction: Cost-Efficient Compaction for Long-Horizon Coding Agents](https://mlsanity.com/paper/2609.26779/) (2026)
- [EvoBelief: Falsifiable World Models for Self-Improving LLM Agents](https://mlsanity.com/paper/2610.12789/) (2026)

## Abstract (arXiv)

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.