Belief-State Engine: Augmenting LLMs for Principled Planning Under Partial Observability

Arnab Chattopadhayay; Debdipta Halder

Source-linked AI summary

Belief-State Engine: Augmenting LLMs for Principled Planning Under Partial Observability

Arnab Chattopadhayay, Debdipta Halder

arXiv:2609.10036v1Sep 9, 2026cs.AIcs.LGcs.RO

TL;DR

Partially observable settings challenge history-conditioned LLM agents because textual histories do not provide an explicit, stable belief over hidden state. The paper introduces an external Bayesian Belief-State Engine, proves belief-MDP soundness under four axioms, and reports stronger evaluation outcomes in some tested comparisons while documenting important scope limitations.

Problem
History-conditioned LLM agents lack an explicit belief representation and can behave inconsistently across belief-equivalent histories under partial observability.
Method
The Belief-State Engine maintains a Bayesian posterior over a POMDP and exposes only that normalized belief to the LLM, with four axioms specifying belief consistency.
Results
The BSE outperforms reactive and natural-language belief-tracker baselines on Tiger, while attack-graph task-return differences are not statistically distinguishable at N = 40.
Takeaways & Limitations
The architecture provides an external, auditable, POMDP-grounded belief substrate that is compositional with belief-measurable LLM policies and linked to classical belief-MDP guarantees.
Takeaways & Limitations
The evaluation omits several baselines and ablations, uses small samples and a single sampling seed, and employs a reduced decision-consistency protocol.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper argues that partially observable environments expose a structural weakness in history-conditioned LLM agents: they lack an explicit, calibrated belief over hidden state. It introduces the external Belief-State Engine, formalizes its guarantees, and evaluates it across two environments and multiple baselines.

Motivation: History-conditioned LLM agents perform well when the next action follows directly from the latest observation but exhibit characteristic failures under partial observability.The paper identifies premature commitment, uncertainty errors, and policy instability as motivating problems.
Architecture: The Belief-State Engine maintains a Bayesian POMDP posterior and exposes only the normalized belief to the LLM at decision time.The raw action-observation trace is withheld from the LLM.
Theory: Under four axioms, the LLM-BSE composition is a sound Markov policy on the belief MDP and inherits classical Bellman optimality guarantees when raw history is excluded.The guarantee depends on belief-measurable action selection and the specified POMDP model.
Evaluation: The empirical study evaluates Tiger and a red-team attack graph against six baselines using task return, belief calibration, decision consistency, and compute cost.The baselines include reactive, Chain-of-Thought, ReAct, a natural-language belief tracker, QMDP, and POMCP.
Positioning: The paper distinguishes explicit, external, auditable probabilistic beliefs from implicit or free-text belief representations used in related LLM-agent hybrids.The BSE is presented as compositional with any belief-measurable LLM policy.

B. LLMs as History-Conditioned Text Policies

The paper models a deployed LLM agent as a history-conditioned text policy: a serializer converts interaction history into a prompt, the LLM samples text, and a parser extracts an action. This formulation remains distinct from an explicit Bayesian belief filter.

Policy construction: A deterministic serializer maps each interaction history to a finite token string supplied as the LLM prompt.The serializer may include a system prompt and a transcript of past actions and observations.
Policy construction: An LLM induces a conditional distribution over token continuations, while an action parser maps outputs to actions or an abstention symbol.Malformed continuations may trigger a default action or retry.
Policy type: Composing serialization, language-model decoding, and parsing yields a policy conditioned on textual history rather than an explicit belief state.The paper treats Chain-of-Thought, reflection, and scratchpad memories as variations on this same policy type.
Bayesian contrast: The belief is the posterior over latent states and can be updated recursively with the Bayes filter from the current belief, action, and next observation.This is the state representation used by belief-based POMDP policies.
Practical constraints: Context truncation, provider-side nondeterminism, and parser failures reduce practical access to the history assumed by the formal policy.The paper treats these as implementation constraints rather than first-order structural objections.

C. Why History Conditioning Is Not Enough

History conditioning is insufficient because different textual histories can share a Bayesian posterior while eliciting different LLM actions, and the LLM must otherwise reconstruct belief from raw text. The paper formalizes belief consistency through four axioms and identifies the canonical posterior as the coarsest valid representation.

Sufficiency failure: LLM serialization is lossy, order-sensitive, and sensitive to semantically equivalent rewrites, so belief-equivalent histories can produce different action distributions.This violates the invariance expected of a belief-measurable policy.
Sufficiency failure: Without an explicit normalized distribution updated by the Bayes filter, the LLM must recover the posterior from raw text on every call.The paper states that this recovery is empirically unreliable and supplies more information than the policy needs.
Canonical representation: The paper proves that the canonical posterior is recursively generated by a uniquely determined Bayes update on the relevant reachable domain.This establishes the posterior as a forced representation rather than an arbitrary design choice.
Axioms: The four axioms require recursive updatability, predictive sufficiency, probabilistic internalization, and a belief-measurable policy.The fourth axiom prevents action selection from using history surface features not encoded in the internal state.
Canonical representation: The canonical posterior satisfies the structural axioms and is the coarsest representation consistent with the required sufficiency properties.Every representation satisfying the first two axioms must determine the canonical posterior through a measurable mapping.

D. Uniqueness of the Update

The paper derives policy, value, ambiguity, and compositionality results from the canonical posterior and Bayes filter. These results connect the external BSE architecture to standard belief-MDP theory.

Update uniqueness: The Bayes update is uniquely determined on reachable beliefs by recursive updatability, with continuity extending equality to the full belief domain.The theorem applies to observations with positive probability on reachable beliefs.
Policy invariance: A belief-consistent policy assigns identical action distributions to histories mapped to the same internal state.This policy invariance follows directly from the belief-measurability axiom.
Value equivalence: Under the canonical posterior, optimal history policies lift optimal belief policies, establishing value equivalence between histories and the belief MDP.The proof reduces the history Bellman recursion to the belief-state recursion.
Ambiguity preservation: Bisimilar latent states retain equal posterior mass because their transition and observation behavior is indistinguishable.With symmetric initial priors, the equality also holds at time zero.
LLM-BSE soundness: When the LLM receives only the belief and uses a measurable belief policy, the LLM-BSE process is Markov on belief-action states and has the same value as its belief-MDP policy.Exposing raw history would void the stated compositionality guarantee.

H. Summary

The BSE implements a model-grounded Bayes filter and exposes the resulting belief to the LLM while excluding raw history. Its implementation restores the full prediction-and-correction update and supports numerical, model, and computational requirements.

Theory: The implementation is framed by axioms and theorems that identify the canonical posterior, derive the Bayes update, and establish belief-MDP equivalence and sound LLM-BSE composition.The supplied passages describe these guarantees but do not provide their full proofs here.
Belief Update: The update predicts through T, weights states by observation likelihoods from Z, normalises the correction, and handles zero-probability observations through a fixed prior-extension convention.The zero-likelihood case is flagged for operator review.
Model Interface: The filter consumes transition and observation kernels at runtime, while reward and discount are reserved for classical planners and the initial prior seeds the initial belief.Finite-state kernels may be represented densely or supplied as structured callables.
Numerical Implementation: The update is the textbook two-step Bayes filter written in an explicit, numerically stable form.Log-space evaluation preserves the result up to floating-point roundoff while improving robustness for highly informative observations.
Architecture: The BSE composes a Bayes filter, belief serialiser, LLM continuation, and action parser while keeping the raw action-observation trace outside the LLM prompt.The filter maintains b_t over latent states using T and Z; the serialiser exposes only that belief.
Revision: The current algorithm restores the omitted prediction step from the TechRxiv v1 version, whose omission produced incorrect posteriors under non-trivial transition kernels.All reported section VII results use the restored algorithm.

D. Belief-to-Prompt Serialisation

The serialisation interface constrains the LLM input to a function of the current belief, while implementation choices trade posterior fidelity and token cost against the fixed-context interface. The architecture remains environment-agnostic, but the reported protocol was reduced by live-API budget constraints.

D. Belief-to-Prompt Serialisation: The serialiser σ maps the current belief to LLM-readable text and must depend on b_t alone, with representation choice varied independently from the policy rule.The experiments use tabular, top-k, and full-support sorted serialisers.
D. Belief-to-Prompt Serialisation: A fixed domain header grounds decoding in the latent and action spaces, while the prompt specifies the desired belief-conditioned decision rule.The protocol varies the policy rule and serialiser as separate axes.
E. LLM Policy Interface: The parser accepts only an exact ACTION schema; malformed outputs become ⊥ and are resolved by one deterministic retry followed by a domain-specific fallback.Fallbacks are logged as a first-class metric.
E. LLM Policy Interface: The LLM is reset and invoked afresh at every step, so its decision function has no implicit dependence on prior turns.The prompt is rebuilt from σ(b_t+1).
F. Complexity: Belief prediction costs O(|S|^2) time for dense T and O(k|S|) for sparse T, while top-k serialisation costs O(|S| log k) and emits O(k) tokens.The top-k variant becomes important when context length, rather than filtering, is the binding constraint.
F. Complexity: The architecture uses one LLM call per step with a fixed-size header and belief-derived prompt, avoiding the growing-log prompt of a reactive baseline.Its practical prompt profile is sub-linear in accumulated history, whereas the theoretical claim is soundness.
G. Implementation Notes: The reference module is under 400 lines, logs filter and parsing state, and transfers between Tiger and attack-graph environments by changing the POMDP model and domain header.The filter, serialiser, and LLM interface remain unchanged across environments.
VI. EXPERIMENTAL METHODOLOGY: The full experimental design specified six baselines, ten ablations, and extensive paired-seed evaluation, but the executed round used a reduced subset because live endpoint costs were prohibitive.The reported design reduction is explicitly distinguished from the intended full protocol.

B. Baselines

The study compares LLM agents that receive observations, reasoning, histories, or textual beliefs with classical belief-space planners, while evaluating return, calibration, consistency, and cost under paired seeds. Budget constraints limited the reported run to Reactive, BSE, and NL-Tracker.

Baseline Design: The six planned baselines comprise four LLM-based agents—Reactive, Chain-of-Thought, ReAct, and natural-language belief tracking—and two classical planners, QMDP and POMCP.Only three were executed in the reported round.
Baseline Design: The NL-Tracker maintains a free-text belief summary, whereas QMDP uses a Bayes-filtered belief with a fully observable-after-one-step approximation and POMCP uses particle-based Monte Carlo planning.These baselines test textual epistemic state and classical belief-space planning against BSE.
Controlled Comparison: LLM baselines share prompts, decoding settings, parsers, and backbone, so their principal variation is whether the prompt contains an observation, reasoning, history, or textual belief.This makes BSE-versus-NL-Tracker differences attributable to belief representation rather than reasoning availability.
Executed Subset: The reported round evaluated only Reactive, BSE, and NL-Tracker because live-API budget constraints prevented running Chain-of-Thought, ReAct, QMDP, and POMCP.This triple isolates probabilistic belief representation while holding the LLM backbone and interface fixed.
Metrics: Evaluation reports task return, belief calibration, decision consistency, and compute cost, with calibration restricted to methods that maintain beliefs.Return uses discounted episode rewards and bootstrap intervals.
Metrics: Decision consistency compares action distributions for histories sharing the same true belief using Jensen-Shannon divergence, for which belief-measurable policies should be zero up to sampling noise.A large value directly signals failure of Axiom A4.
Operational Accounting: Fallback actions are counted rather than silently retried, so reported outcomes reflect the policy observed by a downstream operator.Compute metrics also include prompt and generated tokens, latency, calls, abstentions, and resolution outcomes.
Evaluation Protocol: Paired seeds hold initial states, observation noise, and environmental stochasticity constant across methods, with three LLM sampling seeds in the full protocol.The executed results instead used N = 40 main seeds or N = 25 ablation seeds and one sampling seed.

E. Ablation Grid

The ablation program isolates filter, representation, history, prompting, sampling, and model-size choices, but only three ablations were executed. In the reported Tiger results, BSE outperformed Reactive and NL-Tracker, while removing observation correction produced the predicted open-loop failure.

Ablation Design: The planned ten-ablation grid changes one architectural factor at a time and reports paired differences with bootstrap intervals and Wilcoxon p-values.The factors include filter steps, priors, serialisers, raw history, domain grounding, temperature, and model size.
Ablation Definitions: AB1 removes prediction, AB2 removes observation correction, and AB9 varies sampling temperature; the remaining ablations test priors, posterior truncation, free-text serialisation, raw history, headers, and model size.AB2 is intended to create an open-loop agent, while AB1 recovers the earlier incomplete algorithm.
Executed Ablations: Only AB1, AB2, and AB9 were executed; AB3–AB8 and AB10 remained unrun because of the stated budget constraint.The temperature sweep was evaluated at τ = 1.0 in the executed round.
Robustness Replication: The planned open-weights replication used identical prompts, parsers, environments, and seeds, but it was not run in section VII.It remained part of the designed protocol rather than a reported result.
Reporting Protocol: The main comparison used fixed decoding settings and reported paired returns, bootstrap intervals, calibration trajectories, and distributional summaries of consistency JSD without post-hoc metric selection.The full protocol was reduced because approximately 10^5 live API calls exceeded the study budget.
B. Tiger POMDP: In Tiger, Reactive and NL-Tracker each achieved 32/40 successes and mean discounted return −12.00, while BSE achieved 95.0% success after listening 1.45 times on average and obtained positive mean return.The two baseline methods opened immediately and averaged zero listens.
B. Tiger POMDP: Figure 2 shows exact overlap between Reactive and NL-Tracker, while BSE is the only interval excluding zero; the comparison used N = 40 paired seeds.The figure reports success rate and mean discounted return with 95% bootstrap confidence intervals.
B. Tiger POMDP: AB2 kept entropy at exactly ln 2 and caused 23/25 episodes to time out while listening, whereas AB1 was nearly indistinguishable from standard BSE in Tiger.The AB1 result follows because listening leaves the Tiger state unchanged, so prediction has little effect there.

C. Red-Team Attack Graph

On the attack graph, BSE improved coverage and intrusion incidence but did not clearly separate methods on discounted return. Decision consistency favored BSE over the natural-language tracker, while implementation and evaluation limits constrain interpretation.

BSE achieved the highest network-compromise coverage, 42.1% versus Reactive’s 32.5%.
The three methods’ discounted-return confidence intervals overlapped heavily, and their point-estimate ordering was not statistically distinguishable at N = 40.
BSE reached the highest fraction of episodes with at least one intrusion, 90.0%, while taking 2.58 steps to land its first intrusion versus Reactive’s 1.41.
BSE had median decision-consistency JSD 0, compared with 0.043 for the natural-language tracker, whose IQR reached ln 2.
AB2 left belief entropy at exactly ln 64 and produced the worst coverage, whereas dropping prediction could not be meaningfully tested because the reference transition kernel is the identity.
The executed evaluation omitted Chain-of-Thought, ReAct, QMDP, POMCP, seven ablations, and the full sampling protocol, while attack-graph patch and topology dynamics remain unimplemented.

A. Model Knowledge

The BSE requires a POMDP model and separates belief maintenance from LLM action selection. Its guarantees depend on model alignment, restricted inputs, and scalable filtering, while LLM action quality remains empirical.

Model requirements: The BSE requires a runtime POMDP model, with experiments using environment specifications as the model source.When model parameters are uncertain, a Bayes-adaptive POMDP can extend the belief space to S × Θ.
Model requirements: If the model is misspecified, the BSE’s guarantees do not survive, matching the failure mode of classical belief-MDP planners.
Scalability: Exact tabular filtering scales poorly, but particle, variational, and factored-POMDP filters provide standard replacements with approximate Axiom A1–A3 satisfaction.The reported experiments remain within exact filtering limits, with latent-state spaces up to |S| = 64.
Guarantee boundaries: The soundness theorem certifies a Markov policy on a specified belief MDP, not optimal LLM action selection or robustness to reward misspecification.The architecture isolates belief tracking from the empirical quality of the LLM’s belief-to-action map.
Guarantee boundaries: Soundness requires exposing only belief, keeping prompts stateless, and calibrating the model to the intended environment.The paper remains focused on stationary single-agent POMDPs; multi-agent extensions require beliefs over other agents’ policies.
Design stance: The architecture uses an external Bayesian filter so the LLM receives a structured decision state rather than raw history.The paper frames this division as a thin interface between LLM action selection and classical planning.

APPENDIX A PROOFS OF THEOREMS IN SECTION IV

Appendix A proves that the canonical posterior satisfies the belief-state axioms and supports unique updating, Bellman recursion, and belief-MDP reasoning.

Posterior construction: The canonical posterior starts at µ0 and updates recursively through the Bayes operator Uβ after each action-observation pair.The appendix identifies this recursion as the target representation’s defining update mechanism.
Axiom verification: Predictive sufficiency follows because the posterior equals the conditional distribution of the latent state given the history.The next-observation law therefore depends on history only through the posterior.
Axiom verification: The posterior remains in ∆(S) because Bayesian normalization produces a valid probability distribution on the reachable histories.
Representation characterization: Any representation satisfying the structural axioms factors the posterior through a measurable map, and a posterior-valued representation equals the canonical posterior.
Update uniqueness: The Bayes update is unique on reachable belief-observation triples and everywhere under continuity in the belief argument.
Value equivalence: The belief-MDP Bellman recursion follows by induction for finite horizons and by contraction for infinite-horizon discounted problems.The optimal history policy is obtained from the corresponding greedy belief-MDP policy.

G. Proof of theorem 7

The appendix establishes belief-state invariance results and verifies that belief-measurable policies induce Markov dynamics and value equivalence on the belief MDP.

Bisimulation: POMDP bisimulation preserves equality of posterior probabilities for bisimilar latent states after every history extension.The proof uses the Bayes update and induction from the initial prior.
Soundness: For the LLM-BSE composition, the four axioms hold when the policy is measurable in the belief and the update is Uβ.
Soundness: The belief-action process is Markov because observations depend on the current belief and action, while the next belief and action depend only on the current transition.
Value equivalence: The induced history policy has the same value as its belief-measurable policy on the belief MDP.
Axiom independence: Axioms A1–A4 are mutually independent, with a counterexample representation violating each axiom while satisfying the other three.
Counterexamples: A constant representation can satisfy update, probabilistic, and policy-measurability conditions while failing predictive sufficiency when observations contain state information.
Counterexamples: A rescaled posterior preserves update and sufficiency properties but falls outside ∆(S), demonstrating the distinct role of Axiom A3.
Counterexamples: A policy that additionally depends on history-length parity violates A4 despite using the canonical posterior for A1–A3.

APPENDIX C ENVIRONMENT SPECIFICATIONS

The appendix specifies the exact Tiger and red-team environments, action spaces, prompts, and observation conventions used by the evaluation scripts.

Tiger POMDP: The Tiger environment has two latent states, three actions, two observations, prior µ0 = (0.5, 0.5), γ = 0.95, and a 20-step horizon.
Tiger POMDP: Tiger rewards are −1 for listening, +10 for opening the treasure door, and −100 for opening the tiger door.
Red-team attack graph: The red-team environment uses 64 binary latent states, scan, exploit, and wait actions, binary observations, γ = 0.95, and a 30-step horizon.
Red-team attack graph: In the red-team implementation, scans are informative but all transitions use the identity kernel, leaving patching, exploit state changes, and dependency propagation unimplemented.The identity kernel makes the prediction step a no-op in this reference environment.
Evaluation prompts: The evaluation scripts share system prompts and parsers within each environment while varying the state representation supplied to methods.
Evaluation prompts: Tiger prompts specify the goal, rewards, available actions, and latest sensor observation, with belief-tracker prompts requiring a natural-language belief line before the action.
Evaluation prompts: Belief-conditioned prompts provide the posterior probabilities for tiger-left and tiger-right as the current decision state.

B. Red-Team Attack Graph

The red-team attack-graph evaluation specifies a six-node exploit-and-scan task and reports configuration details for the completed runs. The appendix also documents deviations from the designed protocol, including reduced consistency measurement and unimplemented baselines and ablations.

Task and prompts: The task uses six nodes, rewards successful exploits with +20, penalizes failed exploits with -5, scans with -0.5, and permits waiting at -0.1.Available actions include scanning or exploiting each node and waiting; episodes track already compromised nodes and scan observations.
Task and prompts: The BSE prompt exposes current marginal vulnerability probabilities for all six nodes, while the natural-language tracker receives its previous free-text belief summary.The attack-graph prompts require a per-node belief line and a strictly formatted action line.
Evaluation configuration: Completed main comparisons used gpt-4o with τ = 0.3, 40 paired episode seeds per environment, and one LLM-sampling seed per episode.Malformed completions were retried once at τ = 0.0 before a fixed default action; fallback calls remained included in reported returns and abstention rates.
Evaluation configuration: The reported decision-consistency analysis used up to 8 attack-graph belief-collision groups with K = 5 resamples, rather than the designed 200 pairs with K = 32 resamples.The attack graph yielded 24 pairs, whereas Tiger yielded no qualifying groups and was reported as not measured.
Reported measurements: Mean per-episode latency was 111.6 s for Reactive, 140.5 s for BSE, and 56.6 s for NL-Tracker on the attack graph.The appendix attributes the larger attack-graph latency gap to its longer horizon, T = 30 versus T = 20 for Tiger, and larger average token count per call.
Scope and limitations: Chain-of-Thought, ReAct, QMDP, POMCP, open-weights replication, and ablations AB3–AB8 and AB10 were not implemented in this evaluation round.Consequently, the stated future-run hyperparameters for those methods were not tuned or executed here.