Belief-State Engine: Augmenting LLMs for Principled Planning Under Partial Observability
Arnab Chattopadhayay and Debdipta Halder (independent researchers) place a Bayesian belief tracker outside the LLM and show it only the posterior over latent states, never the raw action-observation log, which makes the pair a sound Markov policy on the belief MDP.
Ask this paper
The diagnosis: LLM agents in partially observable settings commit prematurely on ambiguous feedback, collapse uncertainty onto the wrong hypothesis after one informative observation, and drift as history grows. The authors attribute all three to the agent being a history-conditioned policy with no explicit belief over hidden state.
The architectural fix: The Belief-State Engine maintains a Bayesian posterior over the POMDP's latent states and exposes only that posterior at each decision step. Withholding the raw log is load-bearing, not incidental.
What is proved: A four-axiom specification of belief-consistent internal state, plus a proof that the LLM paired with the engine is a sound Markov policy on the induced belief MDP and therefore inherits classical POMDP Bellman optimality guarantees, conditional on the LLM never seeing raw history.
Evaluation: Tiger POMDP and a red-team attack-graph task against six baselines: reactive LLM, Chain-of-Thought, ReAct, a natural-language belief tracker, QMDP and POMCP. The augmented agent improves task return, belief calibration and decision consistency in both domains.
Ablations: Ten targeted ablations isolate each architectural choice and show the effect is not tied to one model.
Abstract
Large language model agents produce fluent action sequences across a wide range of tasks, yet they fail in characteristic ways once the environment becomes partially observable. Ambiguous feedback pushes them into premature commitments. A single informative observation can collapse their uncertainty onto the wrong hypothesis. Policies drift as the history grows. We trace these symptoms to a common structural cause. An LLM agent, as commonly deployed, is a history-conditioned policy with no explicit belief over hidden state. We propose an architectural fix. The Belief-State Engine (BSE) is an inference module placed outside the LLM. It maintains a Bayesian posterior over the latent states of a given POMDP (Partially Observable Markov Decision Process) model, and at each decision step it exposes only that posterior to the LLM. The raw action-observation log is not shown. We set out a minimal four-axiom specification of what a belief-consistent internal state must satisfy, and prove that the LLM paired with the BSE is a sound Markov policy on the belief MDP induced by the underlying POMDP. It therefore inherits the Bellman optimality guarantees of classical POMDP theory, provided the LLM is never exposed to the raw history. We evaluate the architecture on the Tiger POMDP and a red-team attack-graph task, against six baselines: a reactive LLM, Chain-of-Thought, ReAct, a natural-language belief tracker, QMDP, and POMCP. Across both domains, the BSE-augmented agent improves task return, belief calibration, and decision consistency. Ten targeted ablations isolate the contribution of each architectural choice confirms that the effect is not specific to any one model. Code, environment specifications, prompt templates, and seed logs accompany this paper.