# Agent-BRACE: Decoupling Beliefs from Actions in Long-Horizon Tasks via Verbalized State Uncertainty

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

## Key facts

- Cited by 10 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 36 of its 46 references that are in the map.
- First posted on arXiv 12 May 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 36)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [Mind2Web: Towards a Generalist Agent for the Web](https://mlsanity.com/paper/2306.06070/) (2023)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [A-MEM: Agentic Memory for LLM Agents](https://mlsanity.com/paper/2502.12110/) (2025)
- [Mastering Atari with Discrete World Models](https://mlsanity.com/paper/2010.02193/) (2020)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedback](https://mlsanity.com/paper/2305.14975/) (2023)
- [ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks](https://mlsanity.com/paper/1912.01734/) (2019)
- [Teaching Models to Express Their Uncertainty in Words](https://mlsanity.com/paper/2205.14334/) (2022)
- [WebVoyager: Building an End-to-End Web Agent with Large Multimodal Models](https://mlsanity.com/paper/2401.13919/) (2024)
- [TextWorld: A Learning Environment for Text-based Games](https://mlsanity.com/paper/1806.11532/) (2018)
- [MemAgent: Reshaping Long-Context LLM with Multi-Conv RL-based Memory Agent](https://mlsanity.com/paper/2507.02259/) (2025)
- [MEM1: Learning to Synergize Memory and Reasoning for Efficient Long-Horizon Agents](https://mlsanity.com/paper/2506.15841/) (2025)
- [ACON: Optimizing Context Compression for Long-horizon LLM Agents](https://mlsanity.com/paper/2510.00615/) (2025)
- [Taming Overconfidence in LLMs: Reward Calibration in RLHF](https://mlsanity.com/paper/2410.09724/) (2024)
- [Shaping Belief States with Generative Environment Models for RL](https://mlsanity.com/paper/1906.09237/) (2019)
- [Memory as Action: Autonomous Context Curation for Long-Horizon Agentic Tasks](https://mlsanity.com/paper/2510.12635/) (2025)
- [StateAct: Enhancing LLM Base Agents via Self-prompting and State-tracking](https://mlsanity.com/paper/2410.02810/) (2024)
- [Evaluating Long-Context Reasoning in LLM-Based WebAgents](https://mlsanity.com/paper/2512.04307/) (2025)
- [An Evaluation of Estimative Uncertainty in Large Language Models](https://mlsanity.com/paper/2405.15185/) (2024)
- [Probing neural language models for understanding of words of estimative probability](https://mlsanity.com/paper/2211.03358/) (2022)

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

- [PerspectiveGap: A Benchmark for Multi-Agent Orchestration Prompting](https://mlsanity.com/paper/2606.08878/) (2026)
- [EvoHarness-RL: Learning Self-Evolving Runtime Harness for Long-Horizon LLM Agents](https://mlsanity.com/paper/2608.05446/) (2026)
- [Confident at the moment of action: belief miscalibration in LLM play under hidden information](https://mlsanity.com/paper/2608.24691/) (2026)
- [Towards a Belief-Based World Model for LLM Agents](https://mlsanity.com/paper/2609.00455/) (2026)
- [Decision-Sufficient State Representations: Measuring and Reducing Write-Time Regret](https://mlsanity.com/paper/2609.32805/) (2026)
- [Uncertainty Quantification for LLM Agents: A Taxonomy, an Evaluation Protocol, and an Empirical Study](https://mlsanity.com/paper/2609.07395/) (2026)
- [Replication Without Persistence in Hosted LLMs: Measurement Sensitivity in Action-Time Belief Evaluation](https://mlsanity.com/paper/2609.22478/) (2026)
- [FlowState: Execution State as Memory for Long-Horizon LLM Agents](https://mlsanity.com/paper/2609.34565/) (2026)
- [EvoBelief: Falsifiable World Models for Self-Improving LLM Agents](https://mlsanity.com/paper/2610.12789/) (2026)
- [ANTE: Anticipate, Then Execute -- Learning Internal World Models for Coding Agents from Verified Beliefs](https://mlsanity.com/paper/2610.15368/) (2026)

## Abstract (arXiv)

Large language models (LLMs) are increasingly deployed on long-horizon tasks in partially observable environments, where they must act while inferring and tracking a complex environment state over many steps. This leads to two challenges: partial observability requires maintaining uncertainty over unobserved world attributes, and long interaction history causes context to grow without bound, diluting task-relevant information. A principled solution to both challenges is a belief state: a posterior distribution over environment states given past observations and actions, which compactly encodes history for decision making regardless of episode length. In LLM agents, however, the open-ended nature of text makes it unclear how to represent such a distribution. Therefore, we introduce Agent-BRACE: Agent Belief state Representation via Abstraction and Confidence Estimation, a method that decouples an LLM agent into a belief state model and a policy model, jointly optimized via reinforcement learning. The belief state model produces a structured approximation of the belief distribution: a set of atomic natural language claims about the environment, each annotated with an ordinal verbalized certainty label ranging from certain to unknown. The policy model conditions on this compact, structured approximate belief rather than the full history, learning to select actions under explicit uncertainty. Across long-horizon, partially observable embodied language environments, Agent-BRACE achieves an average absolute improvement of +14.5% (Qwen2.5-3B-Instruct) and +5.3% (Qwen3-4B-Instruct), outperforming strong RL baselines while maintaining a near-constant context window independent of episode length. Further analysis shows that the learned belief becomes increasingly calibrated over the course of an episode as evidence accumulates.