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

# Belief-State Engine: Augmenting LLMs for Principled Planning Under Partial Observability
Source: [https://arxiv.org/html/2609.10036](https://arxiv.org/html/2609.10036)
Arnab Chattopadhayay and Debdipta Halder††thanks:A\.˜Chattopadhayay is an Independent Researcher \(UCL˜Alumni\), Bangalore, India \(e\-mail:[arnab\.chattopadhayay@uclmail\.net](mailto:[email protected])\)\.††thanks:D\.˜Halder is an Independent Researcher \(IIT\-Kharagpur Alumni\), Bangalore, India \(e\-mail:[haldev50@gmail\.com](mailto:[email protected])\)\.††thanks:Manuscript prepared April 2026\. Code, environment specifications, prompt templates, and paired\-seed logs accompanying this preprint are available at[https://github\.com/debdipta\-h/bse\-llm](https://github.com/debdipta-h/bse-llm)\.

###### 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 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, and a replication on an open\-weights backbone confirms that the effect is not specific to any one model\. Code, environment specifications, prompt templates, and seed logs accompany this preprint\.

###### Index Terms:

Large language model agents, belief state, partial observability, POMDP, planning under uncertainty, Bayesian filtering, tool\-augmented LLMs\.

## IIntroduction

Large language models now sit at the centre of a growing class of autonomous agents\. Systems such as ReAct\[[1](https://arxiv.org/html/2609.10036#bib.bib1)\], Reflexion\[[2](https://arxiv.org/html/2609.10036#bib.bib2)\], Tree\-of\-Thoughts\[[3](https://arxiv.org/html/2609.10036#bib.bib3)\], Voyager\[[4](https://arxiv.org/html/2609.10036#bib.bib4)\], and SWE\-agent\[[5](https://arxiv.org/html/2609.10036#bib.bib5)\]wrap an LLM inside a loop that turns text\-level reasoning into multi\-step action sequences, over settings that range from embodied simulation to software repair and web navigation\. These systems share a common failure profile\[[6](https://arxiv.org/html/2609.10036#bib.bib6),[7](https://arxiv.org/html/2609.10036#bib.bib7),[8](https://arxiv.org/html/2609.10036#bib.bib8)\]\. They work well when the next action can be decided from the latest observation\. They stumble once the environment becomes partially observable\. Feedback that is delayed, or ambiguous, or actively deceptive, tends to expose a class of failures that Chain\-of\-Thought prompting does not resolve\.

In our view the issue is architectural, not a question of reasoning depth\. Keeping a calibrated belief over hidden states, and then picking actions with respect to that belief, is what Bayesian filtering gives you\. It is not what Chain\-of\-Thought prompting, a longer context window, or a reflection loop confers on an LLM\. These mechanisms accumulate text\. They do not accumulate probability mass\. Two histories that would yield the same Bayesian posterior can elicit very different action distributions from an LLM whenever their surface texts differ, and that already breaks the most basic consistency requirement of a belief\-measurable policy\. The behaviour this produces has been reported many times: premature commitment when evidence is still ambiguous, over\-confident collapse onto one hypothesis after a single informative observation, and policy drift as the context grows\.

Our fix is to stop asking the LLM to act as a planner under partial observability\. We wrap it in a two\-module system\. An external inference component, which we call the Belief\-State Engine, holds the epistemic state\. The LLM is restricted to selecting actions conditioned on that state\. Concretely, the BSE runs a Bayesian filter over a POMDP model\(T,Z\)\(T,Z\)of the environment, and at each step it hands the LLM a normalised beliefbt∈Δ⁡\(𝒮\)b\_\{t\}\\in\\Delta\(\\mathcal\{S\}\)as the only decision\-time context\. The raw trace of past actions and observations is not shown to the LLM\.

This design has a precise mathematical backing\. Under a minimal four\-axiom specification of belief\-consistent internal state, the LLM paired with the BSE is a Markov policy on the belief MDP induced by the underlying POMDP\. It therefore inherits the Bellman optimality theorems of classical POMDP theory\[[9](https://arxiv.org/html/2609.10036#bib.bib9),[10](https://arxiv.org/html/2609.10036#bib.bib10),[11](https://arxiv.org/html/2609.10036#bib.bib11)\]\. The axioms pin down what qualifies as a belief\-consistent internal state\. The theorems lift the architectural choice into a compositionality guarantee with a well\-defined failure mode: if the LLM is shown the raw history at decision time, Axiom A4 is violated and the guarantee falls with it\.

#### Contributions

This paper makes four contributions\.

1. 1\.*Architecture\.*We introduce the Belief\-State Engine, an LLM\-external and model\-agnostic inference module that maintains a POMDP\-grounded belief and interfaces with any belief\-measurable policy, including an LLM\-parameterised one \([sectionV](https://arxiv.org/html/2609.10036#S5)\)\.
2. 2\.*Theory\.*We set out a minimal four\-axiom characterisation of belief\-consistent internal state and prove six theorems: existence and minimality of the canonical posterior, uniqueness of the Bayes update, value equivalence with the belief MDP, ambiguity preservation under bisimulation, and soundness of the LLM\-BSE composition \([sectionIV](https://arxiv.org/html/2609.10036#S4); full proofs in Appendix A\)\.
3. 3\.*Empirical study\.*We evaluate the BSE on two environments, the Tiger POMDP and a red\-team attack\-graph task, against six baselines \(reactive, Chain\-of\-Thought, ReAct, natural\-language belief tracker, QMDP, POMCP\)\. Four metric families are reported: task return, belief calibration, decision consistency, and compute cost\. Ten architectural ablations and an open\-weights robustness replication accompany the main results \([sectionsVI](https://arxiv.org/html/2609.10036#S6)and[VII](https://arxiv.org/html/2609.10036#S7)\)\.
4. 4\.*Artefact release\.*Code, prompt templates, environment specifications, reward matrices, and paired\-seed logs are published with this preprint\.

#### Paper organisation

[SectionII](https://arxiv.org/html/2609.10036#S2)reviews POMDP theory, LLM\-agent failure modes, and related hybrid work\.[SectionIII](https://arxiv.org/html/2609.10036#S3)fixes notation\.[SectionIV](https://arxiv.org/html/2609.10036#S4)sets out the axiomatic foundations\.[SectionV](https://arxiv.org/html/2609.10036#S5)describes the BSE\.[SectionVI](https://arxiv.org/html/2609.10036#S6)details the experimental methodology\.[SectionVII](https://arxiv.org/html/2609.10036#S7)reports results\.[SectionVIII](https://arxiv.org/html/2609.10036#S8)discusses limitations and approximate belief representations\.[SectionIX](https://arxiv.org/html/2609.10036#S9)concludes\.

## IIBackground and Related Work

### II\-APOMDPs and Belief\-State Theory

Partially observable Markov decision processes, or POMDPs, formalise sequential decision\-making when the state is latent\[[9](https://arxiv.org/html/2609.10036#bib.bib9),[10](https://arxiv.org/html/2609.10036#bib.bib10),[12](https://arxiv.org/html/2609.10036#bib.bib12)\]\. A POMDPM=\(𝒮,𝒜,𝒪,T,Z,R,γ,μ0\)M=\(\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{O\},T,Z,R,\\gamma,\\mu\_\{0\}\)extends the standard MDP by a finite observation space𝒪\\mathcal\{O\}and an observation kernelZ⁡\(o∣s,a\)Z\(o\\mid s,a\)\. Its optimal policy can be written as a function of the belief statebt∈Δ⁡\(𝒮\)b\_\{t\}\\in\\Delta\(\\mathcal\{S\}\), the posterior over latent states given the interaction history\[[13](https://arxiv.org/html/2609.10036#bib.bib13),[10](https://arxiv.org/html/2609.10036#bib.bib10)\]\. The belief is a sufficient statistic for optimal decision\-making\[[14](https://arxiv.org/html/2609.10036#bib.bib14),[11](https://arxiv.org/html/2609.10036#bib.bib11)\]\. Updating it recursively via the two\-step Bayes filter, prediction followed by observation\-conditioned correction, turns the POMDP into a fully observable Markov decision process onΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\), the belief MDP\.

Exact solution of belief MDPs is PSPACE\-hard in the finite\-horizon case, and undecidable in the infinite\-horizon case\[[15](https://arxiv.org/html/2609.10036#bib.bib15)\]\. Several decades of research have produced approximate solvers that scale to useful state sizes\. Point\-based value iteration\[[16](https://arxiv.org/html/2609.10036#bib.bib16)\]and SARSOP\[[17](https://arxiv.org/html/2609.10036#bib.bib17)\]restrict value computation to a representative subset of reachable beliefs\. QMDP\[[18](https://arxiv.org/html/2609.10036#bib.bib18)\]computes a fast heuristic by treating the environment as fully observable after the current step\. POMCP\[[19](https://arxiv.org/html/2609.10036#bib.bib19)\]runs Monte Carlo tree search in belief space via sampled rollouts\. All four methods assume access to the model\(T,Z\)\(T,Z\), or at least to a simulator of it\. Our empirical setup makes the same assumption\. Learning the belief\-state model from data is a separate research thread that we discuss in[sectionVIII](https://arxiv.org/html/2609.10036#S8)\.

### II\-BLLM Agents and Their Failure Modes

Starting with ReAct\[[1](https://arxiv.org/html/2609.10036#bib.bib1)\]and continuing through Reflexion\[[2](https://arxiv.org/html/2609.10036#bib.bib2)\], Tree\-of\-Thoughts\[[3](https://arxiv.org/html/2609.10036#bib.bib3)\], Voyager\[[4](https://arxiv.org/html/2609.10036#bib.bib4)\], SWE\-agent\[[5](https://arxiv.org/html/2609.10036#bib.bib5)\], and the Cognitive Architectures for Language Agents survey\[[20](https://arxiv.org/html/2609.10036#bib.bib20)\], the working template for an LLM agent has been to iterate an LLM over a growing text log of past actions and observations, interleaved with reasoning traces, tool calls, and retrieval\. The template works well when the next action can be decided from the current observation and the cost of long\-context reasoning is affordable\.

Systematic evaluations have mapped the limits of that template\. Valmeekam and co\-authors\[[6](https://arxiv.org/html/2609.10036#bib.bib6),[21](https://arxiv.org/html/2609.10036#bib.bib21)\]show that LLMs do poorly on classical planning problems even with Chain\-of\-Thought\. Liu et al\.\[[7](https://arxiv.org/html/2609.10036#bib.bib7)\]report steep performance drops on agent benchmarks once observations are noisy or delayed\. The standard interpretation in the literature is that the LLM lacks a world model, or a calibrated uncertainty estimate\. Our own position is more specific\. The missing component is a sufficient statistic of history\. No amount of reasoning over raw text recovers what Bayesian conditioning gives automatically\.

### II\-CLLM\-POMDP Hybrids and Belief Tracking

A smaller but growing line of work couples LLMs to some form of explicit state representation\. Reasoning via Planning\[[22](https://arxiv.org/html/2609.10036#bib.bib22)\]uses an LLM as a world model inside MCTS\-style search, but the resulting belief is implicit in the tree\. Du et al\.\[[23](https://arxiv.org/html/2609.10036#bib.bib23)\]have LLMs track symbolic task state for goal\-conditioned learning\. Xie et al\.\[[24](https://arxiv.org/html/2609.10036#bib.bib24)\]and related work interpret in\-context learning itself as implicit Bayesian inference, though the posterior is never surfaced\. In the agent setting, a related strand asks an LLM to act as its own belief\-state approximator, typically by narrating its uncertainty in natural language rather than maintaining an explicit probability distribution\.

Three points distinguish the BSE from this line of work\. First, the belief is external and explicit\. It lives as a probability distribution over a finite latent state space, rather than inside the LLM’s activations or in a free\-text paragraph\. Second, the architecture is compositional\. Any LLM can be dropped into the policy slot, and any belief\-measurable policy is sound by Theorem[9](https://arxiv.org/html/2609.10036#Thmtheorem9)\. Third, the belief is auditable\. At every decision point the full posteriorbtb\_\{t\}is available to the operator, which supports debugging, monitoring, and guarantee checks in a way that implicit or free\-text representations cannot match\. We include a natural\-language belief tracker as a direct baseline in our experiments \([sectionVI](https://arxiv.org/html/2609.10036#S6)\) precisely to test whether the benefit we report comes from*any*epistemic state, or specifically from a*probabilistic*one\.

### II\-DUncertainty and Calibration in LLMs

Outside the agent setting, a parallel literature asks whether LLMs are calibrated\. Kadavath et al\.\[[25](https://arxiv.org/html/2609.10036#bib.bib25)\]find that large models are approximately calibrated on factual question answering\. Kuhn et al\.\[[26](https://arxiv.org/html/2609.10036#bib.bib26)\]extend this to semantic uncertainty in free\-form generation\. Distribution\-free coverage guarantees on single\-shot LLM outputs are available through conformal prediction\[[27](https://arxiv.org/html/2609.10036#bib.bib27)\]\. These results all concern an LLM’s self\-reported confidence on individual questions\. They do not address the distinct problem of maintaining a calibrated posterior over a hidden environment state across a multi\-step trajectory\. That is the problem the BSE targets\.

### II\-EThe Gap

None of the lines reviewed above gives what the BSE gives: an LLM\-external, auditable, POMDP\-grounded belief, maintained in closed form, compositional with any LLM policy backbone, and backed by a compositionality theorem that specifies the conditions under which the composition inherits classical POMDP guarantees\. The rest of the paper develops that construction\.[SectionIII](https://arxiv.org/html/2609.10036#S3)fixes notation\.[SectionIV](https://arxiv.org/html/2609.10036#S4)supplies the axiomatic and theoretical foundation\.[SectionV](https://arxiv.org/html/2609.10036#S5)specifies the engine itself\.

## IIIProblem Setting and Preliminaries

We fix notation in this section and then state the central observation that motivates the rest of the paper: an LLM deployed as a history\-conditioned policy is not a belief\-measurable policy, and that gap is what the Belief\-State Engine closes\.

### III\-APOMDPs and the Belief MDP

LetM=\(𝒮,𝒜,𝒪,T,Z,R,γ,μ0\)M=\(\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{O\},T,Z,R,\\gamma,\\mu\_\{0\}\)be a finite partially observable Markov decision process\[[9](https://arxiv.org/html/2609.10036#bib.bib9),[10](https://arxiv.org/html/2609.10036#bib.bib10),[12](https://arxiv.org/html/2609.10036#bib.bib12)\]\. Here𝒮\\mathcal\{S\}is a finite set of latent states,𝒜\\mathcal\{A\}a finite action set, and𝒪\\mathcal\{O\}a finite observation set\. The transition kernelT:𝒮×𝒜→Δ⁡\(𝒮\)T:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\\Delta\(\\mathcal\{S\}\)maps a state\-action pair to a distribution over next states, withT⁡\(s′∣s,a\):=ℙ⁡\(St\+1=s′∣St=s,At=a\)T\(s^\{\\prime\}\\mid s,a\):=\\mathbb\{P\}\(S\_\{t\+1\}\{=\}s^\{\\prime\}\\mid S\_\{t\}\{=\}s,A\_\{t\}\{=\}a\)\. The observation kernelZ:𝒮×𝒜→Δ⁡\(𝒪\)Z:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\\Delta\(\\mathcal\{O\}\)emitsZ⁡\(o∣s′,a\):=ℙ⁡\(Ot\+1=o∣St\+1=s′,At=a\)Z\(o\\mid s^\{\\prime\},a\):=\\mathbb\{P\}\(O\_\{t\+1\}\{=\}o\\mid S\_\{t\+1\}\{=\}s^\{\\prime\},A\_\{t\}\{=\}a\)after the transition\. The reward functionR:𝒮×𝒜→ℝR:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\\mathbb\{R\}is bounded, the discount factorγ∈\[0,1\)\\gamma\\in\[0,1\), andμ0∈Δ⁡\(𝒮\)\\mu\_\{0\}\\in\\Delta\(\\mathcal\{S\}\)is the initial state distribution\. The agent does not observeStS\_\{t\}at any step\.

At timettthe agent has seen an interaction history

ht=\(a0,o1,a1,o2,…,at−1,ot\)∈ℋt,h\_\{t\}=\(a\_\{0\},o\_\{1\},a\_\{1\},o\_\{2\},\\dots,a\_\{t\-1\},o\_\{t\}\)\\in\\mathcal\{H\}\_\{t\},\(1\)withℋt:=\(𝒜×𝒪\)t\\mathcal\{H\}\_\{t\}:=\(\\mathcal\{A\}\\times\\mathcal\{O\}\)^\{t\}andh0:=∅h\_\{0\}:=\\varnothing\. Letℋ:=⋃t≥0ℋt\\mathcal\{H\}:=\\bigcup\_\{t\\geq 0\}\\mathcal\{H\}\_\{t\}denote the set of all finite histories\. A history\-conditioned policy is a mapπ:ℋ→Δ⁡\(𝒜\)\\pi:\\mathcal\{H\}\\to\\Delta\(\\mathcal\{A\}\)\. The induced trajectory distribution factorises in the standard way:

ℙπ\(S0:T,A0:T−1,O1:T\)=μ0​\(S0\)​∏t=0T−1π⁡\(At∣ht\)×T⁡\(St\+1∣St,At\)​Z​\(Ot\+1∣St\+1,At\)\.\\begin\{split\}\\mathbb\{P\}\_\{\\pi\}\(S\_\{0:T\},A\_\{0:T\-1\},O\_\{1:T\}\)=\{\}&\\mu\_\{0\}\(S\_\{0\}\)\\prod\_\{t=0\}^\{T\-1\}\\pi\(A\_\{t\}\\mid h\_\{t\}\)\\\\ &\{\}\\times T\(S\_\{t\+1\}\\mid S\_\{t\},A\_\{t\}\)\\,Z\(O\_\{t\+1\}\\mid S\_\{t\+1\},A\_\{t\}\)\.\\end\{split\}\(2\)The objective is the expected discounted returnJ⁡\(π\):=𝔼π​\[∑t=0∞γt​R​\(St,At\)\]J\(\\pi\):=\\mathbb\{E\}\_\{\\pi\}\\\!\\big\[\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}R\(S\_\{t\},A\_\{t\}\)\\big\]\.

The belief at timettis the posterior over the latent state given the history:

bt​\(s\):=ℙ⁡\(St=s∣ht,μ0\),bt∈Δ⁡\(𝒮\)\.b\_\{t\}\(s\):=\\mathbb\{P\}\(S\_\{t\}\{=\}s\\mid h\_\{t\},\\mu\_\{0\}\),\\qquad b\_\{t\}\\in\\Delta\(\\mathcal\{S\}\)\.\(3\)The belief admits the recursive Bayes\-filter update\[[13](https://arxiv.org/html/2609.10036#bib.bib13),[14](https://arxiv.org/html/2609.10036#bib.bib14)\]\. Givenbtb\_\{t\}, actionata\_\{t\}, and observationot\+1o\_\{t\+1\}, the posterior att\+1t\{\+\}1is

b¯t\+1​\(s′\)\\displaystyle\\bar\{b\}\_\{t\+1\}\(s^\{\\prime\}\)=∑s∈𝒮T⁡\(s′∣s,at\)​bt​\(s\),\\displaystyle=\\sum\_\{s\\in\\mathcal\{S\}\}T\(s^\{\\prime\}\\mid s,a\_\{t\}\)\\,b\_\{t\}\(s\),\(4\)bt\+1​\(s′\)\\displaystyle b\_\{t\+1\}\(s^\{\\prime\}\)=Z⁡\(ot\+1∣s′,at\)​b¯t\+1​\(s′\)∑s′′∈𝒮Z⁡\(ot\+1∣s′′,at\)​b¯t\+1​\(s′′\)\.\\displaystyle=\\frac\{Z\(o\_\{t\+1\}\\mid s^\{\\prime\},a\_\{t\}\)\\,\\bar\{b\}\_\{t\+1\}\(s^\{\\prime\}\)\}\{\\sum\_\{s^\{\\prime\\prime\}\\in\\mathcal\{S\}\}Z\(o\_\{t\+1\}\\mid s^\{\\prime\\prime\},a\_\{t\}\)\\,\\bar\{b\}\_\{t\+1\}\(s^\{\\prime\\prime\}\)\}\.\(5\)Equation \([4](https://arxiv.org/html/2609.10036#S3.E4)\) is the prediction step\. Equation \([5](https://arxiv.org/html/2609.10036#S3.E5)\) is the observation\-conditioned correction\. The two steps must be performed in order\. Dropping the prediction step, as the algorithm in the TechRxiv version of this work inadvertently did, gives an incorrect posterior wheneverT≠IT\\neq I\. We return to this point when we specify the engine in[sectionV](https://arxiv.org/html/2609.10036#S5)\.

Once the belief is introduced, the POMDPMMis equivalent in value to a fully observable Markov decision process onΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\), known as the belief MDP\. Its transition kernel is

τ\(b′∣b,a\)=∑o∈𝒪ℙ\(o∣b,a\)\[b′=Bayes\(b,a,o\)\],\\tau\(b^\{\\prime\}\\mid b,a\)=\\sum\_\{o\\in\\mathcal\{O\}\}\\mathbb\{P\}\(o\\mid b,a\)\\,\\mathbf\{1\}\\\!\\left\[b^\{\\prime\}=\\mathrm\{Bayes\}\(b,a,o\)\\right\],\(6\)whereℙ⁡\(o∣b,a\)=∑s′,sZ⁡\(o∣s′,a\)​T​\(s′∣s,a\)​b​\(s\)\\mathbb\{P\}\(o\\mid b,a\)=\\sum\_\{s^\{\\prime\},s\}Z\(o\\mid s^\{\\prime\},a\)\\,T\(s^\{\\prime\}\\mid s,a\)\\,b\(s\)is the marginal observation probability andBayes⁡\(b,a,o\)\\mathrm\{Bayes\}\(b,a,o\)is the posterior given by \([4](https://arxiv.org/html/2609.10036#S3.E4)\)–\([5](https://arxiv.org/html/2609.10036#S3.E5)\)\. The belief\-MDP reward isr⁡\(b,a\):=∑sb⁡\(s\)​R​\(s,a\)r\(b,a\):=\\sum\_\{s\}b\(s\)\\,R\(s,a\)\. The optimal value functionV∗V^\{\*\}onΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\)satisfies the Bellman equation\[[10](https://arxiv.org/html/2609.10036#bib.bib10),[11](https://arxiv.org/html/2609.10036#bib.bib11)\]

V∗​\(b\)=maxa∈𝒜⁡\[r⁡\(b,a\)\+γ​∑o∈𝒪ℙ⁡\(o∣b,a\)​V∗​\(Bayes⁡\(b,a,o\)\)\]\.V^\{\*\}\(b\)=\\max\_\{a\\in\\mathcal\{A\}\}\\Big\[r\(b,a\)\+\\gamma\\sum\_\{o\\in\\mathcal\{O\}\}\\mathbb\{P\}\(o\\mid b,a\)\\,V^\{\*\}\\\!\\left\(\\mathrm\{Bayes\}\(b,a,o\)\\right\)\\Big\]\.\(7\)The belief is therefore a sufficient statistic of history for the purposes of optimal decision\-making\. Any policy that is a function ofhth\_\{t\}alone, and that attainsJ⁡\(π\)=V∗​\(μ0\)J\(\\pi\)=V^\{\*\}\(\\mu\_\{0\}\), must be expressible as a function ofbtb\_\{t\}on the support of trajectories induced byπ\\pi\. We use this fact repeatedly in[sectionIV](https://arxiv.org/html/2609.10036#S4)\.

### III\-BLLMs as History\-Conditioned Text Policies

Let𝒳\\mathcal\{X\}denote a token alphabet and letϕ:ℋ→𝒳⋆\\phi:\\mathcal\{H\}\\to\\mathcal\{X\}^\{\\\!\\star\}be a deterministic serialiser that maps a historyhth\_\{t\}to a finite token string, for example a system prompt followed by a transcript of past actions and observations\. Given a decoding temperature and a sampling rule, a language model induces a conditional distributionqLLM​\(y∣x\)q\_\{\\textsc\{LLM\}\}\(y\\mid x\)over token continuationsy∈𝒳⋆y\\in\\mathcal\{X\}^\{\\\!\\star\}given any promptx∈𝒳⋆x\\in\\mathcal\{X\}^\{\\\!\\star\}\. An action parserψ:𝒳⋆→𝒜∪\{⊥\}\\psi:\\mathcal\{X\}^\{\\\!\\star\}\\to\\mathcal\{A\}\\cup\\\{\\bot\\\}extracts an action from the LLM output, mapping malformed continuations to a designated abstain symbol⊥\\bot, which the deployment layer typically resolves by default action or retry\.

Composing these pieces gives a history\-conditioned text policy

πLLM\(a∣ht\):=ℙy∼qLLM\(⋅∣ϕ\(ht\)\)\[ψ\(y\)=a\],a∈𝒜\.\\pi\_\{\\textsc\{LLM\}\}\(a\\mid h\_\{t\}\):=\\mathbb\{P\}\_\{y\\sim q\_\{\\textsc\{LLM\}\}\(\\cdot\\mid\\phi\(h\_\{t\}\)\)\}\\big\[\\psi\(y\)=a\\big\],\\qquad a\\in\\mathcal\{A\}\.\(8\)This is the object that is instantiated, explicitly or implicitly, by every LLM agent architecture in\[[1](https://arxiv.org/html/2609.10036#bib.bib1),[2](https://arxiv.org/html/2609.10036#bib.bib2),[3](https://arxiv.org/html/2609.10036#bib.bib3),[4](https://arxiv.org/html/2609.10036#bib.bib4),[5](https://arxiv.org/html/2609.10036#bib.bib5)\]\. Chain\-of\-Thought prompting, reflection, and scratchpad memories are all variations on the serialiserϕ\\phiand on the parserψ\\psi\. They do not, on their own, change the type of the policy\. It remains a map from histories to action distributions\.

The deployment pipeline of equation \([8](https://arxiv.org/html/2609.10036#S3.E8)\) is subject to practical constraints that the belief formulation is not\. Context\-window truncation replacesϕ⁡\(ht\)\\phi\(h\_\{t\}\)by a lossy prefix\-or\-summary for longtt\. Chat\-style APIs introduce provider\-side non\-determinism inqLLMq\_\{\\textsc\{LLM\}\}even at temperature zero\. The parserψ\\psican fail on malformed outputs\. None of these are first\-order to our argument, but they each reduce the agent’s effective access to the history below what the formalism of equation \([2](https://arxiv.org/html/2609.10036#S3.E2)\) assumes\. We flag them here so that the reader can distinguish implementation artefacts from the structural point we develop next\.

### III\-CWhy History Conditioning Is Not Enough

A natural reading of equation \([8](https://arxiv.org/html/2609.10036#S3.E8)\) is thatπLLM\\pi\_\{\\textsc\{LLM\}\}, by taking the full history as input, has access to everything a belief\-based policy would\. In a measure\-theoretic sense this is correct\. The beliefbtb\_\{t\}is a function ofhth\_\{t\}\(andμ0\\mu\_\{0\}\), so anyσ⁡\(ht\)\\sigma\(h\_\{t\}\)\-measurable policy is at least as expressive as aσ⁡\(bt\)\\sigma\(b\_\{t\}\)\-measurable one\. What the sentence hides is that LLMs do not behave asσ⁡\(ht\)\\sigma\(h\_\{t\}\)\-measurable policies in the formal sense\. They behave asσ⁡\(ϕ⁡\(ht\)\)\\sigma\(\\phi\(h\_\{t\}\)\)\-measurable policies, and the serialiserϕ\\phiis lossy, order\-sensitive, and not invariant to semantically equivalent rewrites of the same history\. We record the two properties that will matter for[sectionIV](https://arxiv.org/html/2609.10036#S4)\.

#### Belief measurability

A history\-conditioned policyπ\\piis*belief measurable*if there existsπ~:Δ⁡\(𝒮\)→Δ⁡\(𝒜\)\\tilde\{\\pi\}:\\Delta\(\\mathcal\{S\}\)\\to\\Delta\(\\mathcal\{A\}\)with

π\(⋅∣h\)=π~\(b\(h\)\)for allh∈ℋ,\\pi\(\\cdot\\mid h\)=\\tilde\{\\pi\}\\\!\\big\(b\(h\)\\big\)\\qquad\\text\{for all \}h\\in\\mathcal\{H\},\(9\)whereb⁡\(h\)b\(h\)is the belief induced byhhunderμ0\\mu\_\{0\}\. Classical POMDP theory shows that an optimal policy can always be chosen to be belief measurable\. The belief MDP onΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\)is the object on which the Bellman equation \([7](https://arxiv.org/html/2609.10036#S3.E7)\) is solved\.

#### Sufficiency failure ofπLLM\\pi\_\{\\textsc\{LLM\}\}

We claim, and make precise in[sectionIV](https://arxiv.org/html/2609.10036#S4), thatπLLM\\pi\_\{\\textsc\{LLM\}\}generically fails to be belief measurable\. Two elementary observations support the claim\.

*Observation 1 \(surface sensitivity\)\.*Two historiesh,h′∈ℋh,h^\{\\prime\}\\in\\mathcal\{H\}withb⁡\(h\)=b⁡\(h′\)b\(h\)=b\(h^\{\\prime\}\)may haveϕ⁡\(h\)≠ϕ⁡\(h′\)\\phi\(h\)\\neq\\phi\(h^\{\\prime\}\)whenever they differ in action\-observation order, token count, formatting, or accumulated reasoning trace\. By constructionqLLM\(⋅∣ϕ\(h\)\)≠qLLM\(⋅∣ϕ\(h′\)\)q\_\{\\textsc\{LLM\}\}\(\\cdot\\mid\\phi\(h\)\)\\neq q\_\{\\textsc\{LLM\}\}\(\\cdot\\mid\\phi\(h^\{\\prime\}\)\)in general, soπLLM\(⋅∣h\)≠πLLM\(⋅∣h′\)\\pi\_\{\\textsc\{LLM\}\}\(\\cdot\\mid h\)\\neq\\pi\_\{\\textsc\{LLM\}\}\(\\cdot\\mid h^\{\\prime\}\)even though both conditioning sets yield the same Bayesian posterior\. No property of the belief mapbbis being used\.

*Observation 2 \(no explicit filter\)\.*Absent a mechanism that carries a normalised distribution over𝒮\\mathcal\{S\}forward across steps and updates it via equations \([4](https://arxiv.org/html/2609.10036#S3.E4)\) and \([5](https://arxiv.org/html/2609.10036#S3.E5)\), the LLM must recover the posterior implicitly from raw text on every call\. Empirically this recovery is unreliable\. It is also, by the sufficiency argument above, more information than the policy needs\.

Together, observations 1 and 2 say thatπLLM\\pi\_\{\\textsc\{LLM\}\}is acting on a representation strictly larger, and in practice strictly noisier, than the belief MDP state\. The architectural question this raises is the one we answer in[sectionV](https://arxiv.org/html/2609.10036#S5): construct an external module that maintainsbtb\_\{t\}in closed form and expose onlybtb\_\{t\}to the LLM\. Section[IV](https://arxiv.org/html/2609.10036#S4)first specifies, by four independent axioms, what it would mean for any internal state \(LLM\-internal, module\-external, or hybrid\) to be belief consistent, and proves that the canonical posterior is the coarsest such object up to measurable relabelling\.

## IVAxiomatic Foundations of Belief Augmentation

This section specifies, with four independent axioms, what any internal state must satisfy for an agent to qualify as belief\-consistent on a given POMDP, and then derives the structural properties that follow\. The canonical posteriorβ\\betaof[definition1](https://arxiv.org/html/2609.10036#Thmdefinition1)is shown to be the coarsest representation consistent with the axioms, the Bayes filter is derived as the unique update operator on the reachable subsimplex, value equivalence with the belief MDP is established, ambiguity preservation under POMDP bisimulation is obtained as a theorem rather than postulated, and soundness of the LLM\-BSE composition is proved\. Full proofs are deferred to Appendix[A](https://arxiv.org/html/2609.10036#A1); the statements below include short sketches\. Independence of the axiom set is verified in Appendix[B](https://arxiv.org/html/2609.10036#A2)\.

### IV\-AThe Canonical Posterior

We first fix the object that plays the role of target representation\. The preliminaries of[sectionIII](https://arxiv.org/html/2609.10036#S3)defined the Bayes update operatorBayes⁡\(⋅,a,o\)\\mathrm\{Bayes\}\(\\cdot,a,o\)via the two steps \([4](https://arxiv.org/html/2609.10036#S3.E4)\)–\([5](https://arxiv.org/html/2609.10036#S3.E5)\)\. We now lift it to histories\.

###### Definition 1\(Canonical posterior\)\.

The*canonical posterior*is the mapβ:ℋ→Δ⁡\(𝒮\)\\beta:\\mathcal\{H\}\\to\\Delta\(\\mathcal\{S\}\)defined recursively byβ⁡\(∅\)=μ0\\beta\(\\varnothing\)=\\mu\_\{0\}and

β⁡\(h⋅\(a,o\)\):=Bayes⁡\(β⁡\(h\),a,o\)\\beta\\\!\\left\(h\\cdot\(a,o\)\\right\):=\\mathrm\{Bayes\}\\\!\\left\(\\beta\(h\),a,o\\right\)\(10\)for everyh∈ℋh\\in\\mathcal\{H\}of positive prior probability\. We writeUβU\_\{\\beta\}for the induced operator onΔ⁡\(𝒮\)×𝒜×𝒪\\Delta\(\\mathcal\{S\}\)\\times\\mathcal\{A\}\\times\\mathcal\{O\}, so thatβ⁡\(h⋅\(a,o\)\)=Uβ​\(β⁡\(h\),a,o\)\\beta\(h\\cdot\(a,o\)\)=U\_\{\\beta\}\(\\beta\(h\),a,o\)\. On the zero\-prior set we fixβ\\betaby an arbitrary measurable convention; this set hasμ0\\mu\_\{0\}\-measure zero and plays no further role\.

### IV\-BAxioms

Fix a POMDPMM\. An*internal representation*is a measurable mapψ:ℋ→𝒳\\psi:\\mathcal\{H\}\\to\\mathcal\{X\}, where\(𝒳,d𝒳\)\(\\mathcal\{X\},d\_\{\\mathcal\{X\}\}\)is a Polish space\. We writebt:=ψ⁡\(ht\)b\_\{t\}:=\\psi\(h\_\{t\}\)and refer toψ⁡\(ℋ\)\\psi\(\\mathcal\{H\}\)as the*reachable set*of the representation\. A policyπ:ℋ→Δ⁡\(𝒜\)\\pi:\\mathcal\{H\}\\to\\Delta\(\\mathcal\{A\}\)is the remaining component of the agent\.

###### Axiom A1\(Recursive Updatability\)\.

There exist a fixed elementx0∈𝒳x\_\{0\}\\in\\mathcal\{X\}and a measurable operatorU:𝒳×𝒜×𝒪→𝒳U:\\mathcal\{X\}\\times\\mathcal\{A\}\\times\\mathcal\{O\}\\to\\mathcal\{X\}withψ⁡\(∅\)=x0\\psi\(\\varnothing\)=x\_\{0\}andψ⁡\(h⋅\(a,o\)\)=U⁡\(ψ⁡\(h\),a,o\)\\psi\(h\\cdot\(a,o\)\)=U\(\\psi\(h\),a,o\)for everyh∈ℋh\\in\\mathcal\{H\}and\(a,o\)∈𝒜×𝒪\(a,o\)\\in\\mathcal\{A\}\\times\\mathcal\{O\}\.

###### Axiom A2\(Predictive Sufficiency\)\.

For allh,h′∈ℋh,h^\{\\prime\}\\in\\mathcal\{H\}withψ⁡\(h\)=ψ⁡\(h′\)\\psi\(h\)=\\psi\(h^\{\\prime\}\), and for everys∈𝒮s\\in\\mathcal\{S\},a∈𝒜a\\in\\mathcal\{A\},o∈𝒪o\\in\\mathcal\{O\},

ℙ⁡\(St=s∣h\)\\displaystyle\\mathbb\{P\}\(S\_\{t\}\{=\}s\\mid h\)=ℙ⁡\(St′=s∣h′\),\\displaystyle=\\mathbb\{P\}\(S\_\{t^\{\\prime\}\}\{=\}s\\mid h^\{\\prime\}\),ℙ⁡\(Ot\+1=o∣h,a\)\\displaystyle\\mathbb\{P\}\(O\_\{t\+1\}\{=\}o\\mid h,a\)=ℙ⁡\(Ot′\+1=o∣h′,a\),\\displaystyle=\\mathbb\{P\}\(O\_\{t^\{\\prime\}\+1\}\{=\}o\\mid h^\{\\prime\},a\),wheret=\|h\|t=\|h\|andt′=\|h′\|t^\{\\prime\}=\|h^\{\\prime\}\|\.

###### Axiom A3\(Probabilistic Internalisation\)\.

𝒳⊆Δ⁡\(𝒮\)\\mathcal\{X\}\\subseteq\\Delta\(\\mathcal\{S\}\), soψ⁡\(h\)\\psi\(h\)is a probability distribution over the latent state space for everyh∈ℋh\\in\\mathcal\{H\}\.

###### Axiom A4\(Belief\-Measurable Policy\)\.

There exists a measurableπ~:𝒳→Δ⁡\(𝒜\)\\tilde\{\\pi\}:\\mathcal\{X\}\\to\\Delta\(\\mathcal\{A\}\)withπ\(⋅∣h\)=π~\(⋅∣ψ\(h\)\)\\pi\(\\cdot\\mid h\)=\\tilde\{\\pi\}\(\\cdot\\mid\\psi\(h\)\)for everyh∈ℋh\\in\\mathcal\{H\}\.

A word on what each axiom does\. Axiom[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)rules out any representation that requires revisiting the raw history at update time\. Axiom[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)pins the information content ofψ\\psito whatever determines the conditional laws of the latent state and of the next observation\. Axiom[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)fixes the coordinate system in which the representation lives and is what earns the term “belief\.” Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)is the architectural constraint\. It forbids the policy from looking at surface features of the history that are not already encoded inψ⁡\(h\)\\psi\(h\)\. Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)are structural properties of the representation; Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)is the formal statement of belief\-action separation\.

### IV\-CExistence and Minimality

We show that the canonical posterior satisfies the structural axioms and is, in a precise sense, the smallest such representation\.

###### Theorem 1\(Existence\)\.

The canonical posteriorβ\\betaof[definition1](https://arxiv.org/html/2609.10036#Thmdefinition1)satisfies Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)\.

*Proof sketch\.*Recursive updatability is immediate from \([10](https://arxiv.org/html/2609.10036#S4.E10)\) withx0=μ0x\_\{0\}=\\mu\_\{0\}andU=UβU=U\_\{\\beta\}\. Predictive sufficiency holds becauseβ⁡\(h\)​\(s\)=ℙ⁡\(St=s∣h\)\\beta\(h\)\(s\)=\\mathbb\{P\}\(S\_\{t\}\{=\}s\\mid h\)by construction, and conditioning the observation law on the latent state gives a formula that depends onhhonly throughβ⁡\(h\)\\beta\(h\)\. Values inΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\)follow from the normalisation in \([5](https://arxiv.org/html/2609.10036#S3.E5)\)\. See Appendix[A](https://arxiv.org/html/2609.10036#A1)\. ∎

###### Theorem 2\(Minimality\)\.

Letψ:ℋ→𝒳\\psi:\\mathcal\{H\}\\to\\mathcal\{X\}satisfy Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)\. Then there exists a measurableg:𝒳→Δ⁡\(𝒮\)g:\\mathcal\{X\}\\to\\Delta\(\\mathcal\{S\}\)withβ⁡\(h\)=g⁡\(ψ⁡\(h\)\)\\beta\(h\)=g\(\\psi\(h\)\)for everyh∈ℋh\\in\\mathcal\{H\}\. Equivalently, every representation consistent with these two axioms is at least as fine asβ\\beta, and at best a lossless re\-encoding of it\.

*Proof sketch\.*Sufficiency impliesβ\\betais constant on the fibres ofψ\\psi, so it factors throughψ\\psi\. The factoring is measurable by a selection theorem on Polish spaces\. See Appendix[A](https://arxiv.org/html/2609.10036#A1)\. ∎

###### Corollary 3\(Canonical coarsest representation\)\.

Under Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A3](https://arxiv.org/html/2609.10036#Thmaxiom3), the representationψ=β\\psi=\\betais the unique \(up toμ0\\mu\_\{0\}\-a\.s\. relabelling\) representation that is both minimal in the sense of[theorem2](https://arxiv.org/html/2609.10036#Thmtheorem2)and valued inΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\)\.

### IV\-DUniqueness of the Update

The Bayes filter is not imposed as an axiom\. It is forced once the representation is fixed toβ\\beta\.

###### Theorem 4\(Uniqueness of the Bayes update\)\.

Letψ=β\\psi=\\betaand letU:Δ⁡\(𝒮\)×𝒜×𝒪→Δ⁡\(𝒮\)U:\\Delta\(\\mathcal\{S\}\)\\times\\mathcal\{A\}\\times\\mathcal\{O\}\\to\\Delta\(\\mathcal\{S\}\)be any operator satisfying Axiom[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)forβ\\beta\. ThenU=UβU=U\_\{\\beta\}on\{\(b,a,o\):b∈β\(ℋ\),ℙ\(o∣b,a\)\>0\}\\\{\(b,a,o\):b\\in\\beta\(\\mathcal\{H\}\),\\mathbb\{P\}\(o\\mid b,a\)\>0\\\}\. If in additionUUis continuous in its first argument, thenU=UβU=U\_\{\\beta\}on all ofΔ⁡\(𝒮\)×𝒜×𝒪\\Delta\(\\mathcal\{S\}\)\\times\\mathcal\{A\}\\times\\mathcal\{O\}\.

*Proof sketch\.*For any reachablebb, pick a historyhhwithβ⁡\(h\)=b\\beta\(h\)=b; recursive updatability forcesU⁡\(b,a,o\)=β⁡\(h⋅\(a,o\)\)=Uβ​\(b,a,o\)U\(b,a,o\)=\\beta\(h\\cdot\(a,o\)\)=U\_\{\\beta\}\(b,a,o\)\. Continuity extends the equality to the closure\. See Appendix[A](https://arxiv.org/html/2609.10036#A1)\. ∎

### IV\-EPolicy and Value Invariance

###### Theorem 5\(Policy invariance\)\.

Under Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A4](https://arxiv.org/html/2609.10036#Thmaxiom4), ifψ⁡\(h\)=ψ⁡\(h′\)\\psi\(h\)=\\psi\(h^\{\\prime\}\)thenπ\(⋅∣h\)=π\(⋅∣h′\)\\pi\(\\cdot\\mid h\)=\\pi\(\\cdot\\mid h^\{\\prime\}\)\.

*Proof sketch\.*Direct application of[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)\. ∎

###### Theorem 6\(Value equivalence\)\.

LetVℋ⋆:ℋ→ℝV\_\{\\mathcal\{H\}\}^\{\\star\}:\\mathcal\{H\}\\to\\mathbb\{R\}be the optimal discounted value function on histories andVΔ⋆:Δ⁡\(𝒮\)→ℝV\_\{\\Delta\}^\{\\star\}:\\Delta\(\\mathcal\{S\}\)\\to\\mathbb\{R\}the optimal value function of the belief MDP \([6](https://arxiv.org/html/2609.10036#S3.E6)\)–\([7](https://arxiv.org/html/2609.10036#S3.E7)\)\. Under Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)withψ=β\\psi=\\beta,

Vℋ⋆​\(h\)=VΔ⋆​\(β⁡\(h\)\)∀h∈ℋ\.V\_\{\\mathcal\{H\}\}^\{\\star\}\(h\)=V\_\{\\Delta\}^\{\\star\}\(\\beta\(h\)\)\\qquad\\forall\\,h\\in\\mathcal\{H\}\.\(11\)An optimal history\-policy is obtained by lifting any optimal belief\-policyπΔ⋆:Δ⁡\(𝒮\)→Δ⁡\(𝒜\)\\pi\_\{\\Delta\}^\{\\star\}:\\Delta\(\\mathcal\{S\}\)\\to\\Delta\(\\mathcal\{A\}\)throughπℋ⋆\(⋅∣h\):=πΔ⋆\(⋅∣β\(h\)\)\\pi\_\{\\mathcal\{H\}\}^\{\\star\}\(\\cdot\\mid h\):=\\pi\_\{\\Delta\}^\{\\star\}\(\\cdot\\mid\\beta\(h\)\)\.

*Proof sketch\.*Finite\-horizon induction onTT\. The observation marginal and the successor belief both factor throughβ\\betaby[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)and the definition ofUβU\_\{\\beta\}, which reduces the Bellman recursion on histories to the Bellman recursion onΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\)\. The infinite\-horizon discounted case follows by a standard contraction argument\[[11](https://arxiv.org/html/2609.10036#bib.bib11)\]\. See Appendix[A](https://arxiv.org/html/2609.10036#A1)\. ∎

### IV\-FAmbiguity Preservation

###### Definition 2\(POMDP bisimulation\)\.

Two latent statess,s′∈𝒮s,s^\{\\prime\}\\in\\mathcal\{S\}are*bisimilar*, writtens∼s′s\\sim s^\{\\prime\}, if for everya∈𝒜a\\in\\mathcal\{A\}:

1. \(i\)Z⁡\(o∣s,a\)=Z⁡\(o∣s′,a\)Z\(o\\mid s,a\)=Z\(o\\mid s^\{\\prime\},a\)for everyo∈𝒪o\\in\\mathcal\{O\};
2. \(ii\)T⁡\(s∣s~,a\)=T⁡\(s′∣s~,a\)T\(s\\mid\\tilde\{s\},a\)=T\(s^\{\\prime\}\\mid\\tilde\{s\},a\)for everys~∈𝒮\\tilde\{s\}\\in\\mathcal\{S\}\.

###### Theorem 7\(Ambiguity preservation\)\.

Ifs∼s′s\\sim s^\{\\prime\}thenβ⁡\(h\)​\(s\)=β⁡\(h\)​\(s′\)\\beta\(h\)\(s\)=\\beta\(h\)\(s^\{\\prime\}\)for every historyhhof lengtht≥1t\\geq 1and every initial priorμ0\\mu\_\{0\}\.

*Proof sketch\.*The ratioβ⁡\(h⋅\(a,o\)\)​\(s\)/β⁡\(h⋅\(a,o\)\)​\(s′\)\\beta\(h\\cdot\(a,o\)\)\(s\)/\\beta\(h\\cdot\(a,o\)\)\(s^\{\\prime\}\)factors as the observation\-kernel ratio times the incoming\-transition\-kernel ratio, both of which equal one under bisimulation\. Induction on history length closes the argument\. See Appendix[A](https://arxiv.org/html/2609.10036#A1)\. ∎

###### Corollary 8\(Strict ambiguity on symmetric priors\)\.

Ifμ0​\(s\)=μ0​\(s′\)\\mu\_\{0\}\(s\)=\\mu\_\{0\}\(s^\{\\prime\}\)ands∼s′s\\sim s^\{\\prime\}, thenβ⁡\(h\)​\(s\)=β⁡\(h\)​\(s′\)\\beta\(h\)\(s\)=\\beta\(h\)\(s^\{\\prime\}\)for every historyhhand everyt≥0t\\geq 0\.

The significance of[theorem7](https://arxiv.org/html/2609.10036#Thmtheorem7)is architectural\. Belief mass on observationally indistinguishable hypotheses is not eliminated by the filter in the absence of discriminative evidence\. The earlier manuscript postulated this property as an independent axiom\. Here it falls out of[definition1](https://arxiv.org/html/2609.10036#Thmdefinition1)and the two bisimulation conditions\.

### IV\-GSoundness of the LLM\-BSE Composition

We close the section with the compositionality result that justifies the architecture developed in[sectionV](https://arxiv.org/html/2609.10036#S5)\.

###### Theorem 9\(Soundness of the LLM\-BSE composition\)\.

LetπLLM:Δ⁡\(𝒮\)→Δ⁡\(𝒜\)\\pi\_\{\\textsc\{LLM\}\}:\\Delta\(\\mathcal\{S\}\)\\to\\Delta\(\\mathcal\{A\}\)be any measurable policy that depends on history only through the belief state, for example an LLM conditioned on a serialisation ofbtb\_\{t\}\. LetU=UβU=U\_\{\\beta\}be the Bayes filter\. Then the composed agent\(Uβ,πLLM\)\(U\_\{\\beta\},\\pi\_\{\\textsc\{LLM\}\}\)satisfies Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A4](https://arxiv.org/html/2609.10036#Thmaxiom4), and the induced stochastic process\(bt,at\)t≥0\(b\_\{t\},a\_\{t\}\)\_\{t\\geq 0\}is a Markov chain onΔ⁡\(𝒮\)×𝒜\\Delta\(\\mathcal\{S\}\)\\times\\mathcal\{A\}with kernel

ℙ\(bt\+1=b′,at\+1=a′\|bt=b,at=a\)=∑o∈𝒪\[b′=Uβ\(b,a,o\)\]ℙ\(o∣b,a\)πLLM\(a′∣b′\)\.\\begin\{split\}&\\mathbb\{P\}\\\!\\left\(b\_\{t\+1\}\{=\}b^\{\\prime\},a\_\{t\+1\}\{=\}a^\{\\prime\}\\,\\big\|\\,b\_\{t\}\{=\}b,a\_\{t\}\{=\}a\\right\)\\\\ &\\quad=\\sum\_\{o\\in\\mathcal\{O\}\}\\mathbf\{1\}\\\!\\left\[b^\{\\prime\}=U\_\{\\beta\}\(b,a,o\)\\right\]\\mathbb\{P\}\(o\\mid b,a\)\\,\\pi\_\{\\textsc\{LLM\}\}\(a^\{\\prime\}\\mid b^\{\\prime\}\)\.\\end\{split\}\(12\)The value ofπLLM\\pi\_\{\\textsc\{LLM\}\}under the LLM\-BSE composition coincides with its value on the belief MDP of[theorem6](https://arxiv.org/html/2609.10036#Thmtheorem6)\.

*Proof sketch\.*The four axioms follow respectively from the choice ofUβU\_\{\\beta\}, from[theorem1](https://arxiv.org/html/2609.10036#Thmtheorem1), frombt∈Δ⁡\(𝒮\)b\_\{t\}\\in\\Delta\(\\mathcal\{S\}\)by construction, and fromπLLM\\pi\_\{\\textsc\{LLM\}\}being belief measurable by hypothesis\. Markovianity of\(bt,at\)\(b\_\{t\},a\_\{t\}\)follows by factoringℙ⁡\(o∣h,a\)\\mathbb\{P\}\(o\\mid h,a\)throughβ⁡\(h\)\\beta\(h\), which is guaranteed by[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)\. The value coincidence is then[theorem6](https://arxiv.org/html/2609.10036#Thmtheorem6)applied withπ~=πLLM\\tilde\{\\pi\}=\\pi\_\{\\textsc\{LLM\}\}\. See Appendix[A](https://arxiv.org/html/2609.10036#A1)\. ∎

### IV\-HSummary

The four axioms reduce to a compact set of design rules for any LLM\-augmented planner operating under partial observability\.[theorems1](https://arxiv.org/html/2609.10036#Thmtheorem1)and[2](https://arxiv.org/html/2609.10036#Thmtheorem2)and[corollary3](https://arxiv.org/html/2609.10036#Thmtheorem3)single out the canonical posterior as the coarsest belief\-consistent representation\.[theorem4](https://arxiv.org/html/2609.10036#Thmtheorem4)derives the Bayes filter as the unique update\.[theorems5](https://arxiv.org/html/2609.10036#Thmtheorem5)and[6](https://arxiv.org/html/2609.10036#Thmtheorem6)establish policy invariance and equivalence with the belief\-MDP value function\.[theorem7](https://arxiv.org/html/2609.10036#Thmtheorem7)and[corollary8](https://arxiv.org/html/2609.10036#Thmtheorem8)guarantee that indistinguishable hypotheses are not eliminated in the absence of evidence\.[theorem9](https://arxiv.org/html/2609.10036#Thmtheorem9)lifts the composition of the Bayes filter with any belief\-measurable LLM policy to a sound Markov policy on the belief MDP\. Independence of Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)is verified in Appendix[B](https://arxiv.org/html/2609.10036#A2)\. The architecture of[sectionV](https://arxiv.org/html/2609.10036#S5)implements exactly this composition\.

## VThe Belief\-State Engine: Architecture

This section specifies the Belief\-State Engine at the level of an implementable system\. We fix the interfaces, write down the belief update as Algorithm[1](https://arxiv.org/html/2609.10036#alg1), describe the belief\-to\- prompt serialiser and the action parser, and report the per\-step time and space complexity\. The theoretical guarantees proved in[sectionIV](https://arxiv.org/html/2609.10036#S4)apply term\-for\-term to the construction below\.

### V\-ASystem Overview

[fig\.1](https://arxiv.org/html/2609.10036#S5.F1)shows the control flow\. The BSE sits between the environment and the LLM\. At each step the environment emits an observationot\+1o\_\{t\+1\}in response to the last actionata\_\{t\}\. The BSE consumes\(at,ot\+1\)\(a\_\{t\},o\_\{t\+1\}\), advances its internal belief frombtb\_\{t\}tobt\+1b\_\{t\+1\}via the two\-step Bayes filter, and handsbt\+1b\_\{t\+1\}to the LLM through a serialiserσ:Δ⁡\(𝒮\)→𝒳⋆\\sigma:\\Delta\(\\mathcal\{S\}\)\\to\\mathcal\{X\}^\{\\\!\\star\}\. The LLM returns a token continuationyt\+1y\_\{t\+1\}, which the parserψ:𝒳⋆→𝒜∪\{⊥\}\\psi:\\mathcal\{X\}^\{\\\!\\star\}\\to\\mathcal\{A\}\\cup\\\{\\bot\\\}converts into an actionat\+1a\_\{t\+1\}\. The raw historyhth\_\{t\}is never part of the LLM prompt\. The system prompt and any in\-context examples are held fixed across steps\.

BSEmoduleEnvironmentPOMDPMMBelief\-State EngineUβU\_\{\\beta\}onΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\)LLMπLLM\(⋅∣b\)\\pi\_\{\\textsc\{LLM\}\}\(\\cdot\\mid b\)bt∈Δ⁡\(𝒮\)b\_\{t\}\\in\\Delta\(\\mathcal\{S\}\)\(at−1,ot\)\(a\_\{t\-1\},o\_\{t\}\)σ⁡\(bt\)\\sigma\(b\_\{t\}\)at=ψ⁡\(yt\)a\_\{t\}=\\psi\(y\_\{t\}\)Fig\. 1:Control flow of the Belief\-State Engine\. The BSE maintains the beliefbt∈Δ⁡\(𝒮\)b\_\{t\}\\in\\Delta\(\\mathcal\{S\}\)by running the two\-step Bayes filterUβU\_\{\\beta\}on the model\(T,Z\)\(T,Z\)\. It exposesbtb\_\{t\}to the LLM through the serialiserσ\\sigma\. The LLM returns a token continuation which the parserψ\\psiconverts intoat∈𝒜a\_\{t\}\\in\\mathcal\{A\}\. The raw action\-observation trace never enters the LLM prompt\.
### V\-BModel Interface

The BSE is parameterised by a POMDP modelM=\(𝒮,𝒜,𝒪,T,Z,R,γ,μ0\)M=\(\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{O\},T,Z,R,\\gamma,\\mu\_\{0\}\)in the sense of[sectionIII\-A](https://arxiv.org/html/2609.10036#S3.SS1)\. The only components that the filter consumes at run time are the transition kernelTTand the observation kernelZZ\. The rewardRRand discountγ\\gammaare used by classical planners that sit alongside the BSE in our experiments \(QMDP, POMCP\); they are not consumed by the filter itself\. The initial priorμ0\\mu\_\{0\}is used to seedb0=μ0b\_\{0\}=\\mu\_\{0\}\.

We keepTTandZZin tabular form for finite\-state domains\. For eacha∈𝒜a\\in\\mathcal\{A\}the kernelT\(⋅∣⋅,a\)T\(\\cdot\\mid\\cdot,a\)is stored as a row\-stochastic matrix of shape\|𝒮\|×\|𝒮\|\|\\mathcal\{S\}\|\\times\|\\mathcal\{S\}\|, and the observation kernelZ\(⋅∣⋅,a\)Z\(\\cdot\\mid\\cdot,a\)as a row\-stochastic matrix of shape\|𝒮\|×\|𝒪\|\|\\mathcal\{S\}\|\\times\|\\mathcal\{O\}\|\. Kernels that exhibit structure \(sparsity, factorisation, or a parametric form\) can be supplied as callables; the filter does not require dense materialisation\. We return to continuous and high\-dimensional𝒮\\mathcal\{S\}in[sectionVIII](https://arxiv.org/html/2609.10036#S8), where variational and particle\-based representations are discussed as drop\-in replacements for the tabular update\.

### V\-CBelief Update: The Two\-Step Bayes Filter

[algorithm1](https://arxiv.org/html/2609.10036#alg1)states the belief update\. It is the textbook Bayes filter of[sectionIII\-A](https://arxiv.org/html/2609.10036#S3.SS1), equations \([4](https://arxiv.org/html/2609.10036#S3.E4)\)–\([5](https://arxiv.org/html/2609.10036#S3.E5)\), written here in an explicit, numerically stable form\.

Algorithm 1Belief\-State Engine: one\-step updateUβU\_\{\\beta\}1:Current belief

b∈Δ⁡\(𝒮\)b\\in\\Delta\(\\mathcal\{S\}\); action

a∈𝒜a\\in\\mathcal\{A\}; observation

o∈𝒪o\\in\\mathcal\{O\}; kernels

T,ZT,Z\.

2:Successor belief

b′∈Δ⁡\(𝒮\)b^\{\\prime\}\\in\\Delta\(\\mathcal\{S\}\)\.

3:Prediction step\.For each

s′∈𝒮s^\{\\prime\}\\in\\mathcal\{S\},

b¯​\(s′\)←∑s∈𝒮T⁡\(s′∣s,a\)​b​\(s\)\.\\bar\{b\}\(s^\{\\prime\}\)\\leftarrow\\sum\_\{s\\in\\mathcal\{S\}\}T\(s^\{\\prime\}\\mid s,a\)\\,b\(s\)\.
4:Observation likelihoods\.For each

s′∈𝒮s^\{\\prime\}\\in\\mathcal\{S\},

ℓ⁡\(s′\)←Z⁡\(o∣s′,a\)\\ell\(s^\{\\prime\}\)\\leftarrow Z\(o\\mid s^\{\\prime\},a\)\.

5:Unnormalised correction\.For each

s′∈𝒮s^\{\\prime\}\\in\\mathcal\{S\},

b~​\(s′\)←ℓ⁡\(s′\)​b¯​\(s′\)\\tilde\{b\}\(s^\{\\prime\}\)\\leftarrow\\ell\(s^\{\\prime\}\)\\,\\bar\{b\}\(s^\{\\prime\}\)\.

6:Normaliser\.

η←∑s′∈𝒮b~​\(s′\)\\eta\\leftarrow\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}\\tilde\{b\}\(s^\{\\prime\}\)\.

7:if

η=0\\eta=0then

8:*Zero\-probability observation under the current model\.*Fall back on the prior\-extension convention of[definition1](https://arxiv.org/html/2609.10036#Thmdefinition1)and flag for operator review\.

9:else

10:

b′​\(s′\)←b~​\(s′\)/ηb^\{\\prime\}\(s^\{\\prime\}\)\\leftarrow\\tilde\{b\}\(s^\{\\prime\}\)/\\etafor every

s′∈𝒮s^\{\\prime\}\\in\\mathcal\{S\}\.

11:endif

12:return

b′b^\{\\prime\}\.

Two remarks on numerical implementation are in order\.

#### Log\-space evaluation

For domains in which a single observation is highly informative relative to the prior, the unnormalised productℓ⁡\(s′\)​b¯​\(s′\)\\ell\(s^\{\\prime\}\)\\,\\bar\{b\}\(s^\{\\prime\}\)can underflow\. We compute the correction in log space,log⁡b~​\(s′\)=log⁡ℓ⁡\(s′\)\+log⁡b¯​\(s′\)\\log\\tilde\{b\}\(s^\{\\prime\}\)=\\log\\ell\(s^\{\\prime\}\)\+\\log\\bar\{b\}\(s^\{\\prime\}\), subtractmaxs′​log​b~​\(s′\)\\max\_\{s^\{\\prime\}\}\\log\\tilde\{b\}\(s^\{\\prime\}\)before exponentiating, and renormalise\. The result is identical to[algorithm1](https://arxiv.org/html/2609.10036#alg1)on IEEE\-754 arithmetic up to floating\-point roundoff and is more robust on high\-likelihood observations\.

#### Zero\-likelihood events

Line[7](https://arxiv.org/html/2609.10036#alg1.l7)catches the case in which the predicted observation marginal is zero\. Under the correct POMDP model this cannot happen on trajectories induced byMM, so any occurrence signals either a model specification error or an environment whose observation channel admits events outside𝒪\\mathcal\{O\}\. The engine logs the event and continues with an arbitrary but fixed extension ofβ\\beta, which is formally what[definition1](https://arxiv.org/html/2609.10036#Thmdefinition1)prescribes on the zero\-prior set\. This behaviour is not a safeguard, it is a diagnostic\. Operators inspecting the logs can distinguish an incorrect\(T,Z\)\(T,Z\)from a benign simulator quirk\.

#### On the TechRxiv v1 algorithm

The version of Algorithm 1 published in the TechRxiv preprint\[[28](https://arxiv.org/html/2609.10036#bib.bib28)\]applied only the observation\-weighted correction and omitted the prediction step\.[algorithm1](https://arxiv.org/html/2609.10036#alg1)restores the full Bayes filter\. The omission produced an incorrect posterior whenever the transition kernel was non\-trivial, which is the standard case\. Every result we report in[sectionVII](https://arxiv.org/html/2609.10036#S7)uses[algorithm1](https://arxiv.org/html/2609.10036#alg1)as written\.

### V\-DBelief\-to\-Prompt Serialisation

The serialiserσ:Δ⁡\(𝒮\)→𝒳⋆\\sigma:\\Delta\(\\mathcal\{S\}\)\\to\\mathcal\{X\}^\{\\\!\\star\}is the interface through which the LLM sees the belief\. Its design is constrained by Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4): the output must be a function ofbtb\_\{t\}alone, with no dependence onhth\_\{t\}\. Beyond that,σ\\sigmais free to choose any representation that the LLM can parse reliably\. We use three serialisers in our experiments, selected to isolate the effect of representation choice\.

The first is a tabular serialiser\. It writes each latent state on its own line, together with the current posterior probability to four decimal places and a human\-readable state label drawn from the domain specification\. The second is a top\-kkserialiser, which reports only thekkstates of largest posterior mass, together with their probabilities, and collapses the remaining mass into a residual entry\. The third is a full\-support sorted serialiser, which lists all latent states sorted by posterior mass\. In all three, the support is always explicit and the probabilities always normalise to one\. No free\-text narrative of the belief is used; the LLM receives structured numerical input\.

The serialiser also carries a fixed domain header, independent oftt, that names the latent\-state space, the action space, and the reward structure\. The header makes the LLM’s decoding grounded in the semantics of𝒮\\mathcal\{S\}and𝒜\\mathcal\{A\}rather than in ambient priors acquired during pretraining\. A persistent system prompt describes the decision rule we want the LLM to execute: “select the action that maximises the expected immediate reward under the belief we provide, and break ties uniformly\.” Any belief\-measurable policy can be specified this way\. The experimental protocol varies the policy rule and the serialiser as independent axes \([sectionVI](https://arxiv.org/html/2609.10036#S6)\)\.

### V\-ELLM Policy Interface

Given the promptσ⁡\(bt\)\\sigma\(b\_\{t\}\), the LLM produces a token continuationyt\+1∼qLLM\(⋅∣σ\(bt\)\)y\_\{t\+1\}\\sim q\_\{\\textsc\{LLM\}\}\(\\cdot\\mid\\sigma\(b\_\{t\}\)\)\. The parserψ:𝒳⋆→𝒜∪\{⊥\}\\psi:\\mathcal\{X\}^\{\\\!\\star\}\\to\\mathcal\{A\}\\cup\\\{\\bot\\\}extracts an action\. We restrictψ\\psito exact\-match parsing on a fixed output schema\. The LLM is instructed to emit a single line of the formACTION: <action\-name\>with<action\-name\>drawn from the serialised action menu; any other output maps to⊥\\bot\.

The abstain symbol⊥\\botis resolved by the deployment layer rather than inside the LLM\. Our protocol is conservative: on a⊥\\bot, we resample once at temperature zero, and if the second output is still malformed, we fall back on a deterministic default action specified per\-domain \(for Tiger,listen; for the attack graph,no\-op\-scan\)\. The fallback rate is logged as a first\-class metric \([sectionVI](https://arxiv.org/html/2609.10036#S6)\) so that the comparison against history\-conditioned baselines does not silently benefit from retries\.

The LLM is invoked fresh at every step\. Token\-level state from stepttdoes not leak into stept\+1t\+1because the BSE rebuilds the prompt fromσ⁡\(bt\+1\)\\sigma\(b\_\{t\+1\}\)\. Chat\-style APIs that carry hidden server state are wrapped in a per\-step reset\. This keeps the LLM’s decision function in the form of Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4), namelyπ~\(⋅∣bt\)\\tilde\{\\pi\}\(\\cdot\\mid b\_\{t\}\), without any implicit dependence on past turns\.

### V\-FComplexity

The per\-step cost of the BSE decomposes into three parts\.

#### Belief update

The prediction step is a dense matrix\-vector product against a slice ofTT, costingO⁡\(\|𝒮\|2\)O\(\|\\mathcal\{S\}\|^\{2\}\)time andO⁡\(\|𝒮\|\)O\(\|\\mathcal\{S\}\|\)auxiliary space\. The observation likelihood is anO⁡\(\|𝒮\|\)O\(\|\\mathcal\{S\}\|\)lookup\. The correction and normaliser areO⁡\(\|𝒮\|\)O\(\|\\mathcal\{S\}\|\)\. For sparseTTwith at mostkknon\-zeros per row, the prediction step drops toO⁡\(k​\|𝒮\|\)O\(k\|\\mathcal\{S\}\|\)\. The update is constant in\|𝒜\|\|\\mathcal\{A\}\|and\|𝒪\|\|\\mathcal\{O\}\|\.

#### Serialisation

The tabular serialiser runs inO⁡\(\|𝒮\|\)O\(\|\\mathcal\{S\}\|\)time and emitsO⁡\(\|𝒮\|\)O\(\|\\mathcal\{S\}\|\)tokens\. The top\-kkserialiser runs inO⁡\(\|𝒮\|​log⁡k\)O\(\|\\mathcal\{S\}\|\\log k\)time with a partial sort and emitsO⁡\(k\)O\(k\)tokens\. For large\|𝒮\|\|\\mathcal\{S\}\|the top\-kkvariant is the operative option, because the LLM’s context budget rather than the filter’s cost becomes the binding constraint\.

#### LLM call

The LLM cost dominates the per\-step budget in practice\. Denote byCLLM​\(n\)C\_\{\\textsc\{LLM\}\}\(n\)the wall\-clock cost of a single generation at a prompt length ofnntokens\. Per step, the architecture calls the LLM once at prompt lengthO⁡\(\|σ⁡\(bt\)\|\)\+O⁡\(\|header\|\)O\(\|\\sigma\(b\_\{t\}\)\|\)\+O\(\|\\text\{header\}\|\), which is orders of magnitude smaller than the growing\-log prompt used by a reactive LLM baseline\. ATT\-step episode therefore costsT⋅CLLM​\(\|σ\|\+c\)T\\cdot C\_\{\\textsc\{LLM\}\}\(\|\\sigma\|\+c\)for a constant header of sizecc, compared with∑t=0T−1CLLM​\(c\+t⋅ℓstep\)\\sum\_\{t=0\}^\{T\-1\}C\_\{\\textsc\{LLM\}\}\(c\+t\\cdot\\ell\_\{\\text\{step\}\}\)for a baseline whose prompt grows byℓstep\\ell\_\{\\text\{step\}\}tokens per step\. The sub\-linear prompt\-length profile is a practical byproduct of the architecture; it is not the theoretical case for the BSE\. The theoretical case is soundness \([theorem9](https://arxiv.org/html/2609.10036#Thmtheorem9)\)\.

#### Memory

The filter keeps a single vectorbt∈ℝ\|𝒮\|b\_\{t\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\}across steps, forO⁡\(\|𝒮\|\)O\(\|\\mathcal\{S\}\|\)persistent memory\. No trajectory buffer is required\.

### V\-GImplementation Notes

The reference implementation of the BSE is a Python module of under 400 lines\. It exposes three objects: aPOMDPModeldataclass carrying\(T,Z,R,γ,μ0\)\(T,Z,R,\\gamma,\\mu\_\{0\}\); aBeliefFilterclass holding the current belief and implementing[algorithm1](https://arxiv.org/html/2609.10036#alg1)in log space; and aSerialiserinterface with the three strategies described above\. The LLM client is a thin wrapper over provider SDKs with a deterministic\-seed option where the provider supports it\. Every call, response, parse outcome, and filter step is logged with a step index, the pre\-update belief, the incoming\(a,o\)\(a,o\), and the post\-update belief, which supports the paired\-seed analysis of[sectionVI](https://arxiv.org/html/2609.10036#S6)and the trajectory\-level debugging we use in the ablation study\.

The module is environment\-agnostic\. Swapping from the Tiger POMDP to the attack\-graph environment is a change to thePOMDPModelinstance and the domain header\. No code in the filter, the serialiser, or the LLM interface changes across environments\. That property, not benchmark numbers, is what the architecture is designed to support, and it is the property the experiments are designed to verify\.

## VIExperimental Methodology

This section states the full experimental protocol as designed, in a form that a reader should be able to reproduce without reference to our code\. We describe the two environments, the six baselines, the four metric families, the paired\-seed comparison rule, the ten\-entry ablation grid, and the open\-weights replication\. Details that do not affect reproducibility \(hyperparameter sweeps for the classical planners, seed lists, wall\-clock totals\) are relegated to Appendix[E](https://arxiv.org/html/2609.10036#A5)\. Prompt templates and environment transition/observation tables are in Appendices[C](https://arxiv.org/html/2609.10036#A3)and[D](https://arxiv.org/html/2609.10036#A4)\.

Executing this protocol in full against a live, paid LLM endpoint requires on the order of10510^\{5\}API calls, which was outside the budget of this study\.[sectionVII\-A](https://arxiv.org/html/2609.10036#S7.SS1)states precisely which subset of the design below was actually run for the numbers reported in[sectionVII](https://arxiv.org/html/2609.10036#S7)– three of the six baselines,N=40N=40\(main\) orN=25N=25\(ablations\) paired seeds rather thanN=300×3N=300\\times 3, three of the ten ablations, and no open\-weights run – and why that subset was chosen\. We retain the full design in this section, rather than trimming it to only what was run, because it is the specification we intend future work \(including our own\) to execute against; each subsection below flags what was and was not part of the executed round\.

### VI\-AEnvironments

Two environments are used\. The first is the canonical Tiger POMDP\[[12](https://arxiv.org/html/2609.10036#bib.bib12)\], which fixes the smallest possible latent space on which the sufficiency gap of[sectionIII\-C](https://arxiv.org/html/2609.10036#S3.SS3)can already be exhibited\. The second is a red\-team attack\-graph task, whose latent space is large enough that the history\-conditioned baselines cannot brute\-force the posterior from the raw trace\.

#### Tiger POMDP

Latent states𝒮=\{left,right\}\\mathcal\{S\}=\\\{\\text\{left\},\\text\{right\}\\\}; actions𝒜=\{listen,open\-left,open\-right\}\\mathcal\{A\}=\\\{\\text\{listen\},\\text\{open\-left\},\\text\{open\-right\}\\\}; observations𝒪=\{hear\-left,hear\-right\}\\mathcal\{O\}=\\\{\\text\{hear\-left\},\\text\{hear\-right\}\\\}\. Transition kernel:listenleaves the state unchanged; eitheropenaction resets the state to a fresh uniform draw\. Observation kernel: underlisten,Z⁡\(hear\-left∣left\)=Z⁡\(hear\-right∣right\)=0\.85Z\(\\text\{hear\-left\}\\mid\\text\{left\}\)=Z\(\\text\{hear\-right\}\\mid\\text\{right\}\)=0\.85; under eitheropen, the observation is uniform\. Reward:R⁡\(listen\)=−1R\(\\text\{listen\}\)=\-1,R⁡\(open\-correct\)=\+10R\(\\text\{open\-correct\}\)=\+10,R⁡\(open\-wrong\)=−100R\(\\text\{open\-wrong\}\)=\-100\. Discountγ=0\.95\\gamma=0\.95; horizonT=20T=20; initial prior uniform\. These numbers match the canonical specification in\[[12](https://arxiv.org/html/2609.10036#bib.bib12)\]and the reference implementations in\[[16](https://arxiv.org/html/2609.10036#bib.bib16),[17](https://arxiv.org/html/2609.10036#bib.bib17),[19](https://arxiv.org/html/2609.10036#bib.bib19)\]\.

#### Red\-team attack graph

A parametric attack\-graph benchmark withKKhost\-service nodes arranged as a directed acyclic graph\. Each node carries a binary latent state in\{vulnerable,hardened\}\\\{\\text\{vulnerable\},\\text\{hardened\}\\\}\. The full latent space is𝒮=\{0,1\}K\\mathcal\{S\}=\\\{0,1\\\}^\{K\}, with\|𝒮\|=2K\|\\mathcal\{S\}\|=2^\{K\}\. We run two scales:K=4K=4\(small,\|𝒮\|=16\|\\mathcal\{S\}\|=16\) andK=6K=6\(medium,\|𝒮\|=64\|\\mathcal\{S\}\|=64\)\. The action set is𝒜=\{scan​\(i\),exploit​\(i\),patch​\(i\),wait\}\\mathcal\{A\}=\\\{\\text\{scan\}\(i\),\\text\{exploit\}\(i\),\\text\{patch\}\(i\),\\text\{wait\}\\\}fori∈\{1,…,K\}i\\in\\\{1,\\dots,K\\\}, giving\|𝒜\|=3​K\+1\|\\mathcal\{A\}\|=3K\+1\. Observations are binary per\-scan reports in𝒪=\{0,1\}\\mathcal\{O\}=\\\{0,1\\\}with false\-positive rateα=0\.1\\alpha=0\.1and false\-negative rateβ=0\.15\\beta=0\.15, so thatZ⁡\(1∣vulnerable,scan​\(i\)\)=1−βZ\(1\\mid\\text\{vulnerable\},\\text\{scan\}\(i\)\)=1\-\\betaandZ​\(1∣hardened,scan​\(i\)\)=αZ\(1\\mid\\text\{hardened\},\\text\{scan\}\(i\)\)=\\alpha\. Transition dynamics:patch​\(i\)\\text\{patch\}\(i\)sets nodeiihardened with probabilityppatch=0\.9p\_\{\\text\{patch\}\}=0\.9;exploit​\(i\)\\text\{exploit\}\(i\)on a vulnerableiisucceeds with probability that depends on the upstream compromise state per the attack\-graph semantics of\[[29](https://arxiv.org/html/2609.10036#bib.bib29)\];waitpasses time\. Reward:R⁡\(scan\)=−0\.5R\(\\text\{scan\}\)=\-0\.5,R⁡\(patch\)=−1R\(\\text\{patch\}\)=\-1,R⁡\(exploit\-success\)=\+20R\(\\text\{exploit\-success\}\)=\+20,R⁡\(exploit\-fail\)=−5R\(\\text\{exploit\-fail\}\)=\-5,R⁡\(wait\)=−0\.1R\(\\text\{wait\}\)=\-0\.1\. Discountγ=0\.95\\gamma=0\.95; horizonT=30T=30\. The initial prior is the maximum\-entropy distribution consistent with any deterministic prior information supplied by the task instance\. Full transition and observation tables are in Appendix[C](https://arxiv.org/html/2609.10036#A3)\.

Two environments, each with a small and a medium configuration for the attack graph, gives four environment instances in total\. The Tiger POMDP anchors the comparison to a well\-understood canonical benchmark\. The attack graph stresses the dependence of each method on explicit belief maintenance in a regime where surface\-text reasoning becomes unwieldy\.

### VI\-BBaselines

Six baselines are reported\. The first four use the same LLM backbone as the BSE\-augmented agent; the last two are classical POMDP planners with no LLM component\.

1. 1\.Reactive LLM\.The prompt contains only the fixed domain header and the most recent observationoto\_\{t\}\. The LLM is instructed to select an action\. No scratchpad, no history, no belief\.
2. 2\.Chain\-of\-Thought \(CoT\)\.The prompt contains the fixed domain header, the current observation, and a cue to reason step by step before emittingACTION: <name\>\. The LLM’s reasoning is discarded across steps\.
3. 3\.ReAct\[[1](https://arxiv.org/html/2609.10036#bib.bib1)\]\.The prompt contains the fixed domain header and a growing text log of past\(thought, action, observation\)triples\. The LLM emits a new thought and action at each step\. History grows monotonically until the context budget is exhausted, at which point the oldest entries are dropped\.
4. 4\.Natural\-language belief tracker\.The prompt contains the fixed domain header and a free\-text belief summary maintained by the LLM itself\. At each step the LLM is asked to \(i\) update its belief in natural language given\(at−1,ot\)\(a\_\{t\-1\},o\_\{t\}\), and \(ii\) emit an action\. The belief summary att\+1t\+1becomes the prompt input att\+1t\+1, replacing the previous one\. This baseline isolates whether the benefit we report comes from any epistemic state or specifically from a probabilistic one\.
5. 5\.QMDP\[[18](https://arxiv.org/html/2609.10036#bib.bib18)\]\.The classical approximation that treats the environment as fully observable after the current step\. The policy isπQMDP\(b\)=arg​maxa∑sb\(s\)QMDP\(s,a\)\\pi\_\{\\text\{QMDP\}\}\(b\)=\\argmax\_\{a\}\\sum\_\{s\}b\(s\)\\,Q^\{\\text\{MDP\}\}\(s,a\), withQMDPQ^\{\\text\{MDP\}\}computed once by exact value iteration on the underlying MDP\. Belief is maintained by the same Bayes filter the BSE uses\.
6. 6\.POMCP\[[19](https://arxiv.org/html/2609.10036#bib.bib19)\]\.Partially Observable Monte Carlo Planning, run with10,00010\{,\}000simulations per decision, a UCB1 exploration constant tuned on a held\-out set of instances, and a rollout depth matched to the horizon\. Belief is represented as a particle set of size256256\.

For the four LLM\-based baselines we use identical system prompts, identical temperature and sampling settings, and identical parsers to the BSE\-augmented agent\. The only variation across them is what the prompt contains: observation, observation\-plus\-reasoning, history log, or textual belief\. This matters for interpretability of the comparison: any difference in performance between the BSE\-augmented agent and the natural\-language belief tracker, for example, is attributable to the representation of the belief, not to the presence or absence of reasoning\.

*Executed subset\.*Budget constraints on live API calls \([sectionVII\-A](https://arxiv.org/html/2609.10036#S7.SS1)\) meant only three of these six baselines were run for the results in[sectionVII](https://arxiv.org/html/2609.10036#S7): Reactive, the BSE\-augmented agent, and the natural\-language belief tracker\. This triple is not an arbitrary convenience sample: it is the minimal set that isolates the paper’s central claim, that the benefit comes from a*probabilistic*belief representation specifically rather than from maintaining*any*epistemic state\. Reactive has no belief at all; the NL\-Tracker has an explicit but non\-probabilistic belief;BSEhas an explicit probabilistic belief; holding the LLM backbone, prompt structure, and parser fixed across all three isolates that one factor\. Chain\-of\-Thought, ReAct, QMDP, and POMCP were not run in this round and remain part of the designed protocol for future work\.

### VI\-CMetrics

Four families of metrics are reported\. The first concerns task performance\. The second concerns belief calibration, which is only defined for methods that maintain a belief\. The third concerns decision consistency in the sense of Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)\. The fourth concerns cost\.

#### Task return

Per episode, we report the undiscounted return∑t=0T−1R⁡\(st,at\)\\sum\_\{t=0\}^\{T\-1\}R\(s\_\{t\},a\_\{t\}\)and the discounted return∑t=0T−1γt​R​\(st,at\)\\sum\_\{t=0\}^\{T\-1\}\\gamma^\{t\}R\(s\_\{t\},a\_\{t\}\)\. Per run, we report the mean overN=300N=300episodes together with a bootstrap95%95\\%confidence interval \(10,000 resamples\)\. Pairs of methods are compared via the paired\-seed protocol below\.

#### Belief calibration

For methods that maintain a belief over𝒮\\mathcal\{S\}, we report three measures computed at each step using oracle access to the true latent statest⋆s\_\{t\}^\{\\star\}\(which is available to the evaluator but never to the agent\):

Brier​\(bt\)\\displaystyle\\text\{Brier\}\(b\_\{t\}\)=∑s∈𝒮\(bt\(s\)−𝟏\[s=st⋆\]\)2,\\displaystyle=\\sum\_\{s\\in\\mathcal\{S\}\}\\left\(b\_\{t\}\(s\)\-\\mathbf\{1\}\[s\{=\}s\_\{t\}^\{\\star\}\]\\right\)^\{2\},NLL​\(bt\)\\displaystyle\\text\{NLL\}\(b\_\{t\}\)=−log⁡bt​\(st⋆\),\\displaystyle=\-\\log b\_\{t\}\(s\_\{t\}^\{\\star\}\),H⁡\(bt\)\\displaystyle H\(b\_\{t\}\)=−∑s∈𝒮bt\(s\)logbt\(s\)\.\\displaystyle=\-\\sum\_\{s\\in\\mathcal\{S\}\}b\_\{t\}\(s\)\\log b\_\{t\}\(s\)\.The first two score accuracy against ground truth;HHtracks the residual uncertainty\. We report the mean trajectory of each measure overtt, together with a per\-episode summary \(terminal Brier, terminal NLL, area under the entropy curve\)\. For the natural\-language belief tracker we extract a probability vector by matching per\-state numerical mentions in the belief summary and renormalising; malformed outputs are coded as uniform and flagged\.

#### Decision consistency

We sample200200pairs of distinct histories\(h,h′\)\(h,h^\{\\prime\}\)per environment such thatβ⁡\(h\)=β⁡\(h′\)\\beta\(h\)=\\beta\(h^\{\\prime\}\)under the true model\. The target property is thatπ\(⋅∣h\)=π\(⋅∣h′\)\\pi\(\\cdot\\mid h\)=\\pi\(\\cdot\\mid h^\{\\prime\}\)whenever the agent is belief measurable \([theorem5](https://arxiv.org/html/2609.10036#Thmtheorem5)\)\. We measure the deviation from this property by the Jensen\-Shannon divergence between the two action distributions,

JSD\(h,h′\)=12KL\(π\(⋅∣h\)∥m\)\+12KL\(π\(⋅∣h′\)∥m\),\\text\{JSD\}\(h,h^\{\\prime\}\)=\\tfrac\{1\}\{2\}\\mathrm\{KL\}\(\\pi\(\\cdot\\mid h\)\\,\\\|\\,m\)\+\\tfrac\{1\}\{2\}\\mathrm\{KL\}\(\\pi\(\\cdot\\mid h^\{\\prime\}\)\\,\\\|\\,m\),\(13\)withm=12\(π\(⋅∣h\)\+π\(⋅∣h′\)\)m=\\tfrac\{1\}\{2\}\(\\pi\(\\cdot\\mid h\)\+\\pi\(\\cdot\\mid h^\{\\prime\}\)\)\. For stochastic policies \(the LLM\-based baselines at nonzero temperature\),π\(⋅∣h\)\\pi\(\\cdot\\mid h\)is estimated fromK=32K=32independent completions\. For a belief\-measurable policy,JSD​\(h,h′\)\\text\{JSD\}\(h,h^\{\\prime\}\)should be zero up to sampling noise\. A large value is a direct failure of Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)\.

#### Compute

Per step: prompt length in tokens, generated tokens, wall\-clock latency\. Per episode: total tokens, total wall\-clock, number of LLM calls, number of parser abstentions⊥\\bot, and the abstention resolution outcome\. POMCP reports simulations per decision in place of LLM calls\.

### VI\-DPaired\-Seed Comparison Protocol

Every method is evaluated on the same list ofN=300N=300episode seeds per environment instance\. A seed fixes the initial latent state sample, the per\-step observation noise, and any environmental stochasticity\. The same seed therefore drives every method on the same environment instance, so that differences in performance are attributable to the method rather than to differences in the trajectory distribution\.

For LLM methods, we additionally fix the sampling seed at temperatureτ=0\.3\\tau=0\.3for the main comparison, and reportτ∈\{0\.0,0\.3,0\.7\}\\tau\\in\\\{0\.0,0\.3,0\.7\\\}in the ablation grid\. Each episode is repeated with three independent LLM\-sampling seeds, yielding900900LLM\-backed episodes per method per environment\. The paired\-seed structure supports Wilcoxon signed\-rank tests on paired returns and per\-seed bootstrap confidence intervals, both of which we report\.

*Executed subset\.*The results in[sectionVII](https://arxiv.org/html/2609.10036#S7)useN=40N=40paired seeds per environment instance for the main comparison andN=25N=25for the ablation grid, each with a single LLM\-sampling seed rather than three, so the confidence intervals reported there are correspondingly wider than the full protocol would give\.

All LLM calls are logged with the prompt, the full completion, the parse outcome, the parsed action, and any fallback resolution\. Calls that fall back to the default action are counted but not retried against the ideal parse, so the reported numbers reflect the policy a downstream operator would actually observe\.

### VI\-EAblation Grid

Ten ablations isolate the architectural choices of[sectionV](https://arxiv.org/html/2609.10036#S5)\. Each ablation modifies exactly one factor relative to the BSE\-augmented agent and is run on the full paired\-seed protocol\.

1. AB1\.*Drop prediction step\.*Recovers the TechRxiv v1 algorithm\. The correction step is applied tobtb\_\{t\}directly, without the transition push\-through\. Expected effect: severe degradation on the attack graph, mild on Tiger\.
2. AB2\.*Drop observation step\.*The belief is pushed throughTTbut never corrected byZZ; the agent becomes open\-loop\. Expected effect: uniform degradation\.
3. AB3\.*Wrong initial prior\.*μ0\\mu\_\{0\}replaced by a non\-uniform Dirichlet draw fixed per episode\. Isolates the contribution of prior correctness\.
4. AB4\.*Top\-kkserialiser,k=1k=1\(MAP only\)\.*Only the most likely state is shown to the LLM\. Tests whether full posterior mass carries decision\-relevant information beyond the mode\.
5. AB5\.*Top\-kkserialiser,k=3k=3\.*Mid\-fidelity serialisation for the attack\-graph case\.
6. AB6\.*Free\-text belief description\.*Replace the tabular serialiser with a templated natural\-language description of the same posterior\. Distinguishes structural from surface effects\.
7. AB7\.*Expose raw history\.*Concatenate the lastn=5n=5\(a,o\)\(a,o\)pairs to the belief prompt, violating Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)\. Expected effect: degraded decision consistency and possibly degraded returns\.
8. AB8\.*Omit domain header\.*Strip the fixed semantic header from the prompt\. Tests whether the LLM’s pretraining priors can substitute for domain grounding\.
9. AB9\.*Temperature sweep\.*Evaluateτ∈\{0\.0,0\.3,0\.7,1\.0\}\\tau\\in\\\{0\.0,0\.3,0\.7,1\.0\\\}holding all else fixed\.
10. AB10\.*Model\-size sweep\.*Swap the LLM backbone between the primary model and a smaller variant \(same provider family\), with all other components held constant\.

The ablations are reported as a grid of paired\-comparison differences against the main BSE\-augmented configuration, with95%95\\%bootstrap intervals and Wilcoxonpp\-values\.

*Executed subset\.*Of these ten, three were run for[sectionVII](https://arxiv.org/html/2609.10036#S7):AB1\(drop prediction step\),AB2\(drop observation step\), andAB9\(temperature sweep, evaluated atτ=1\.0\\tau=1\.0only\)\. These three were prioritised because they test the two components of the Bayes filter itself \(prediction, correction\) and one non\-architectural control \(sampling temperature\), within the same budget constraint noted in[sectionVI\-B](https://arxiv.org/html/2609.10036#S6.SS2)\.AB3–AB8andAB10were not run in this round\.

### VI\-FOpen\-Weights Replication

To check that the effect is not specific to a single proprietary backbone, we replicate the main comparison \(BSE\-augmented agent versus the four LLM baselines\) on an open\-weights model in the Qwen family, sized to the largest variant that fits in our inference hardware at bfloat16 precision\. The replication uses identical prompts, identical parsers, identical environments, and identical seeds\. We report absolute returns and calibration numbers for the open\-weights runs, and relative differences against the primary runs, so that the reader can distinguish a uniform model\-family effect from an architecture\-specific one\.

*Executed subset\.*This replication was not run for[sectionVII](https://arxiv.org/html/2609.10036#S7), for the same live\-API budget reason given in[sectionVI\-B](https://arxiv.org/html/2609.10036#S6.SS2); it remains part of the designed protocol rather than a reported result\.

### VI\-GPrimary LLM and Fixed Configuration

The primary LLM for the main comparison and the ablations is the latest production\-general\-purpose checkpoint in its family\. All calls use the same system prompt and the same decoding settings: temperatureτ=0\.3\\tau=0\.3, top\-p=0\.95p=0\.95, maximum generation length256256tokens, and a fixed seed where the provider API exposes one\. These settings are held constant across all LLM methods in the main comparison; the temperature\-sweep ablation \(AB9\) is the only place where they vary\.

### VI\-HStatistical Reporting

Primary comparisons are reported with the mean return per episode, the paired\-seed Wilcoxon signed\-rankpp\-value against every other method, and the bootstrap95%95\\%confidence interval on the mean\. We do not report standard errors in isolation; they would understate variance on paired data\. Calibration numbers are reported with their trajectory means, terminal values, and bootstrap intervals\. Decision\-consistency JSD values are reported as median, interquartile range, and maximum, because the distribution is skewed and the upper tail carries the signal\.

No post\-hoc metric selection is performed\. The four metric families, the six baselines, and the ten ablations are fixed before any run against the primary LLM, and the log of a dry run on a smaller model is used only for parser debugging\.

## VIIResults

### VII\-AScope of the Reported Evaluation

The full protocol of[sectionVI](https://arxiv.org/html/2609.10036#S6)specifies six baselines,N=300N=300paired seeds×\\timesthree LLM\-sampling seeds per environment instance, and ten ablations\. Executing that protocol against a live, paid LLM endpoint requires on the order of10510^\{5\}API calls, which was outside the budget of this study\. We report a deliberately reduced live evaluation instead, and state the reduction explicitly rather than presenting it as the full protocol\.

Three of the six baselines are evaluated:*Reactive*, theBSE\-augmented agent, and the*natural\-language belief tracker*\(NL\-Tracker\)\. This triple is chosen because the BSE\-versus\-NL\-Tracker comparison directly targets the paper’s central claim: that the benefit comes from a probabilistic belief representation specifically, not from maintaining any epistemic state at all\. Chain\-of\-Thought, ReAct, QMDP, and POMCP are not evaluated here\. The main comparison usesN=40N=40paired seeds per environment instance and the ablation grid usesN=25N=25seeds, both with a single LLM\-sampling seed, rather thanN=300×3N=300\\times 3\. Of the ten ablations in[sectionVI\-E](https://arxiv.org/html/2609.10036#S6.SS5), three are evaluated:AB1\(drop prediction step\),AB2\(drop observation step\), andAB9\(temperature sweep,τ=1\.0\\tau=1\.0\)\. All numbers below usegpt\-4oatτ=0\.3\\tau=0\.3for the main comparison, matching[sectionVI\-G](https://arxiv.org/html/2609.10036#S6.SS7)\. The open\-weights replication of[sectionVI\-F](https://arxiv.org/html/2609.10036#S6.SS6)was not run\. Confidence intervals are correspondingly wide, especially on the attack graph; point estimates should be read as suggestive rather than confirmatory\.

### VII\-BTiger POMDP

[TableI](https://arxiv.org/html/2609.10036#S7.T1)reports the main comparison on the canonical two\-state Tiger POMDP \(T=20T=20,γ=0\.95\\gamma=0\.95,N=40N=40paired seeds\)\.

TABLE I:Tiger POMDP main comparison \(N=40N=40paired seeds,T=20T=20,γ=0\.95\\gamma=0\.95,gpt\-4o,τ=0\.3\\tau=0\.3\)\.Reactive and the NL\-Tracker produce*identical*aggregate outcomes: 32/40 successful episodes, mean discounted return−12\.00\-12\.00, and zerolistenactions on average\. Both open a door on the very first turn in every episode, wagering directly on the raw 85%\-accurate sensor reading; a first\-turn open succeeds with probability 0\.85 in theory, and32/40=80%32/40=80\\%is consistent with that within sampling noise\. Maintaining an explicit natural\-language belief did not change the NL\-Tracker’s behaviour at all relative to Reactive, which is given no belief whatsoever\.

BSE, given only the exact Bayes posterior with no worked\-out decision threshold in its prompt \([sectionVI\-B](https://arxiv.org/html/2609.10036#S6.SS2)\), listens 1\.45 times on average before committing and reaches 95\.0% success with a positive mean return, against both baselines’ negative mean return\. This is the sufficiency\-gap prediction of[sectionIII\-C](https://arxiv.org/html/2609.10036#S3.SS3)made concrete: an explicit probabilistic belief, not the mere presence of a belief representation, is what lets the policy compound evidence before acting\.

The decision\-consistency probe of[sectionVI\-C](https://arxiv.org/html/2609.10036#S6.SS3)found zero qualifying belief\-collision history pairs for all three methods atN=40N=40in this environment \(see[sectionVII\-D](https://arxiv.org/html/2609.10036#S7.SS4)\); we report this as not measured rather than assume it to be zero\.

![Refer to caption](https://arxiv.org/html/2609.10036v1/tiger_main_results.png)Fig\. 2:Tiger POMDP main comparison: success rate \(left\) and mean discounted return with 95% bootstrap CI \(right\),N=40N=40paired seeds\. Generated directly fromlogs/2026\-09\-02/tiger\_full\_eval\_results\.json\.[Figure2](https://arxiv.org/html/2609.10036#S7.F2)plots the same numbers as[tableI](https://arxiv.org/html/2609.10036#S7.T1): Reactive and the NL\-Tracker overlap exactly, andBSE’s confidence interval is the only one that excludes zero\.

Ablations\.[TableII](https://arxiv.org/html/2609.10036#S7.T2)reports the three implemented ablations against the standardBSEconfiguration,N=25N=25seeds each\.

TABLE II:Tiger POMDP ablations \(N=25N=25seeds each\)\.†23/25 episodes time out still listening\.

AB2produces the theoretically expected clean failure: with no observation correction the belief never leaves the uniform prior \(entropy pinned at exactlyln⁡2\\ln 2\), the agent sees an identical prompt every turn, and 23/25 episodes simply time out still listening – a textbook open\-loop degradation\.AB1is nearly indistinguishable from standardBSE, exactly as expected: thelistentransition kernel is already the identity, so dropping the prediction step changes nothing except immediately after a door\-opening reset, which does not recur within an episode\.AB9\(τ=1\.0\\tau=1\.0\) is not conclusively worse than the standard configuration at this sample size\.

![Refer to caption](https://arxiv.org/html/2609.10036v1/tiger_ablation_results.png)Fig\. 3:Tiger POMDP ablations: mean discounted return with 95% bootstrap CI \(left\) and mean belief entropy \(right\),N=25N=25seeds each\. AB2’s entropy is pinned at exactlyln⁡2≈0\.693\\ln 2\\approx 0\.693, the open\-loop signature described in the text\.
### VII\-CRed\-Team Attack Graph

[TableIII](https://arxiv.org/html/2609.10036#S7.T3)reports the main comparison on theK=6K=6attack graph \(\|𝒮\|=64\|\\mathcal\{S\}\|=64,T=30T=30,γ=0\.95\\gamma=0\.95,N=40N=40paired seeds;patchexcluded from the action menu because its transition dynamics are an unimplemented placeholder in the reference environment,[sectionVI\-A](https://arxiv.org/html/2609.10036#S6.SS1)\)\.

TABLE III:Attack\-graph main comparison \(K=6K=6,\|𝒮\|=64\|\\mathcal\{S\}\|=64,N=40N=40paired seeds,T=30T=30,γ=0\.95\\gamma=0\.95,gpt\-4o,τ=0\.3\\tau=0\.3\)\.Unlike the Tiger domain, this comparison does not cleanly separate the methods on task return: all three 95% bootstrap confidence intervals overlap heavily, and the point\-estimate ordering \(NL\-Tracker\>\>BSE\>\>Reactive\) is not statistically distinguishable at this sample size\.BSEdoes show the highest network\-compromise coverage \(42\.1% vs\. Reactive’s 32\.5%\) and the highest fraction of episodes with at least one intrusion \(90\.0%\), consistent with more deliberate reconnaissance before committing to an exploit; it also takes longer to land its first intrusion \(2\.58 steps vs\. Reactive’s 1\.41\)\.

The metric that does clearly separateBSEfrom the NL\-Tracker is decision consistency: the NL\-Tracker’s median JSD across belief\-equivalent history pairs \(0\.043, IQR reachingln⁡2\\ln 2\) is measurably worse thanBSE’s \(median 0, tighter IQR\) – the free\-text belief format induces more action\-distribution drift across histories the true posterior treats as equivalent, a direct manifestation of the kind of Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)violation the format is prone to\. This separation is visible even where raw return is not\.

![Refer to caption](https://arxiv.org/html/2609.10036v1/attack_main_results.png)Fig\. 4:Attack\-graph main comparison: network compromise coverage \(left\) and mean discounted return with 95% bootstrap CI \(right\),N=40N=40paired seeds\. Unlike the Tiger domain, the three return intervals overlap heavily\.Ablations\.[TableIV](https://arxiv.org/html/2609.10036#S7.T4)reports the same three ablations on the attack graph,N=25N=25seeds each\.

TABLE IV:Attack\-graph ablations \(N=25N=25seeds each\)\.†Near\-null effect caused by an identity transition kernel in the reference environment, not a substantive finding; see text\.

AB2again shows the theoretically expected clean failure: entropy pinned at exactlyln⁡64\\ln 64\(the belief never leaves the uniform prior\) and the worst coverage of the four configurations\.AB1 shows almost no degradation here, which contradicts the severe\-degradation prediction of[sectionVI\-E](https://arxiv.org/html/2609.10036#S6.SS5); the reason is a known limitation of the reference environment rather than a substantive empirical finding\. The transition kernelTTimplemented for the attack graph is the identity matrix for every action \(exploit and patch dynamics are an unimplemented placeholder,[sectionVI\-A](https://arxiv.org/html/2609.10036#S6.SS1)\), so dropping the prediction step drops an operation that was already a no\-op\. This ablation cannot demonstrate the effect the paper predicts until real state\-dependent transition dynamics are implemented for this environment\.AB9is not conclusively worse than standardBSEat this sample size\.

We additionally note that the ablation run’s StandardBSEconfiguration and the main comparison’sBSErow use an identical prompt and temperature but were separate live API calls, and do not match numerically even on overlapping seeds \(e\.g\. 84\.0% vs\. 95\.0% success in Tiger, mean return6\.106\.10vs\.−2\.80\-2\.80on the attack graph\)\. This is consistent withgpt\-4onot being deterministic across separate calls atτ=0\.3\\tau=0\.3, a limitation discussed further in[sectionVIII](https://arxiv.org/html/2609.10036#S8)\.

![Refer to caption](https://arxiv.org/html/2609.10036v1/attack_ablation_results.png)Fig\. 5:Attack\-graph ablations: mean discounted return with 95% bootstrap CI \(left\) and network compromise coverage \(right\),N=25N=25seeds each\. AB2 shows the lowest coverage of the four configurations, consistent with the open\-loop failure discussed in the text\.
### VII\-DSummary and Honest Limitations of This Evaluation

This evaluation supports a clear version of the paper’s central claim on the canonical Tiger POMDP:BSEoutperforms both a purely reactive baseline and a natural\-language belief tracker on task return, success rate, and calibration, with a plausible causal mechanism \(more information\-gathering actions before commitment\)\. It does*not*support an equally clean version of the same claim on the larger attack\-graph environment: task\-return differences are not statistically distinguishable atN=40N=40, thoughBSEand the NL\-Tracker separate clearly from Reactive on decision consistency and network\-compromise coverage\.

This evaluation does not test Chain\-of\-Thought, ReAct, QMDP, or POMCP; the open\-weights replication of[sectionVI\-F](https://arxiv.org/html/2609.10036#S6.SS6); or seven of the ten ablations \(AB3–AB8, AB10\)\. Sample sizes \(N=40N=40/2525, single LLM\-sampling seed\) are an order of magnitude smaller than theN=300×3N=300\\times 3protocol of[sectionVI](https://arxiv.org/html/2609.10036#S6), so the confidence intervals above should be read accordingly\. The decision\-consistency measurement is itself a reduced, opportunistic version of the protocol in[sectionVI\-C](https://arxiv.org/html/2609.10036#S6.SS3): rather than 200 pre\-selected pairs withK=32K=32resamples, up to 10 \(Tiger\) / 8 \(attack graph\) belief\-collision groups are found from the main run’s own trajectories and resampledK=5K=5times each; Tiger yielded zero qualifying groups atN=40N=40, the attack graph yielded 24 pairs\. Finally, the attack graph’spatchaction and node\-dependency lateral\-movement topology are unimplemented in the reference environment \(the transition kernel is the identity for every action, and node vulnerability is drawn i\.i\.d\. rather than propagated through graph topology\); this limits what AB1 and AB2 can demonstrate there, as discussed above\.

## VIIILimitations and Approximate Belief Representations

We list the assumptions under which the theorems of[sectionIV](https://arxiv.org/html/2609.10036#S4)and the architecture of[sectionV](https://arxiv.org/html/2609.10036#S5)apply, together with the routes by which each can be relaxed\.

### VIII\-AModel Knowledge

The BSE requires a POMDP model\(T,Z\)\(T,Z\)at run time\. In the experiments of[sectionVI](https://arxiv.org/html/2609.10036#S6)the model is given by the environment specification, which is the standard setup for canonical benchmarks and for operator\-controlled decision support tools such as a red\-team attack planner with a documented system inventory\. Three reductions of the requirement are worth noting\.

When the model is uncertain rather than unknown, the POMDP can be replaced by a Bayes\-adaptive POMDP in which the parameters ofTTandZZare themselves latent random variables\. The belief now ranges over𝒮×Θ\\mathcal\{S\}\\times\\ThetawithΘ\\Thetathe parameter space; the Bayes filter is still well defined and the axioms of[sectionIV](https://arxiv.org/html/2609.10036#S4)are satisfied with𝒳=Δ⁡\(𝒮×Θ\)\\mathcal\{X\}=\\Delta\(\\mathcal\{S\}\\times\\Theta\)\. The cost is the usual one: the belief is higher\-dimensional, and the exact update becomes intractable unlessΘ\\Thetais finite or conjugate priors are available\.

When the model must be learned from data, the BSE becomes the downstream consumer of a belief\-state model rather than its definition\. Work on learning latent\-state models from interaction traces, from offline logs, or from an LLM prior on domain semantics, all fits in the same slot: swap[algorithm1](https://arxiv.org/html/2609.10036#alg1)from a tabular kernel evaluation to a learned transition and emission model\. The soundness theorem \([theorem9](https://arxiv.org/html/2609.10036#Thmtheorem9)\) continues to hold in the sense that the composite agent is a Markov policy on the learned belief MDP; the soundness claim relative to the true environment, however, is only as strong as the learned model’s fidelity\.

When the model is outright misspecified, none of the guarantees survive\. This is not special to the BSE\. Classical belief\-MDP planners inherit the same failure mode\.

### VIII\-BFinite Latent Spaces

[algorithm1](https://arxiv.org/html/2609.10036#alg1)presumes\|𝒮\|\|\\mathcal\{S\}\|small enough to materialise the posterior as a vector\. The axioms themselves are not so restricted\. Axiom[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)places the representation inΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\), which is well defined on any measurable𝒮\\mathcal\{S\}, and Axiom[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)accepts any measurable update operator\. What breaks at scale is the filter, not the theory\.

Three drop\-in replacements for the tabular filter are standard\. Particle filters representbtb\_\{t\}by a weighted sample and update via sequential Monte Carlo; amortised variational posteriors representbtb\_\{t\}by the parameters of a distribution family and update via a learned recognition network; in factored POMDPs, a dynamic Bayesian network structure lets the filter exploit conditional independence\. Each of these is a sound instantiation of the BSE in the sense of Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)up to the approximation error of the chosen filter class, and[theorem6](https://arxiv.org/html/2609.10036#Thmtheorem6)then holds only up to a corresponding error term\. Quantifying that error for the variational and particle regimes is the subject of a companion line of work and is not the subject of the present paper\.

For the experiments we report, the finite\-state tabular regime is sufficient: the Tiger POMDP is binary and the largest attack\-graph configuration we evaluate has\|𝒮\|=64\|\\mathcal\{S\}\|=64, which remains well within the domain of exact belief updates\.

### VIII\-CLLM Provider Non\-Determinism

Commercial LLM APIs do not guarantee bitwise\-identical outputs across calls with identical inputs, even at temperature zero\. Sources include batching, silent model updates, and provider\-side kernel replacements\. This affects every result we report through the LLM\-policy componentπLLM\\pi\_\{\\textsc\{LLM\}\}\. We mitigate the exposure by running paired seeds on the same day for any pair of methods under comparison, by freezing the model checkpoint where the provider exposes a versioned endpoint, and by reporting three independent LLM\-sampling seeds per episode\. The open\-weights replication of[sectionVI\-F](https://arxiv.org/html/2609.10036#S6.SS6)removes the provider dependency altogether and lets the reader separate a provider artefact from a genuine architectural effect\.

The BSE itself is deterministic up to floating\-point roundoff\. Any run\-to\-run variance in reported numbers is attributable toqLLMq\_\{\\textsc\{LLM\}\}and to environment seeds, and the logging protocol of[sectionV\-G](https://arxiv.org/html/2609.10036#S5.SS7)records enough information to attribute each difference to its source after the fact\.

### VIII\-DReward Specification

The soundness theorem speaks about Bellman optimality on the belief MDP defined by a given reward function\. If the reward is misspecified in the sense that it fails to capture what the operator actually wants, the guarantee is technically intact but practically vacuous\. This is a shared limitation of reinforcement learning and classical POMDP planning, not something specific to the BSE\. What the BSE does add is a clean substrate on which to iterate on the reward without retraining any LLM component: the LLM policyπ~\\tilde\{\\pi\}can be respecified per task by the system prompt, and the filter is reward\-free\.

### VIII\-EScope of the Soundness Claim

[theorem9](https://arxiv.org/html/2609.10036#Thmtheorem9)asserts that the composite\(Uβ,πLLM\)\(U\_\{\\beta\},\\pi\_\{\\textsc\{LLM\}\}\)is a Markov policy on the belief MDP and that its value equals that ofπLLM\\pi\_\{\\textsc\{LLM\}\}as a belief\-measurable policy\. It does not assert thatπLLM\\pi\_\{\\textsc\{LLM\}\}is optimal\. The LLM component is the parameterisation of the belief\-to\-action map, and its quality is ultimately empirical\. The contribution of the architecture is to isolate that quality\. Given the BSE, the question “how well does the LLM pick actions from a given posterior?” becomes answerable independently of “how well does the LLM track a posterior from a raw history?”\.

Three precondition reminders apply\. The LLM must be given the belief and only the belief\. Violating this is the content of ablation AB7\. The prompt must be stateless across steps\. Violating this recovers a variant of ReAct\. The model\(T,Z\)\(T,Z\)must be the one the agent intends the belief to be calibrated to\. Violating this takes the soundness claim to a statement about the model rather than the environment\.

### VIII\-FSingle\-Agent and Stationary Setting

The present paper stays inside the stationary single\-agent POMDP\. Multi\-agent extensions require a decentralised POMDP or an interactive POMDP formulation, with a belief over other agents’ policies as well as the latent environment state\. The axiomatic framework transports to the interactive case once the state space is extended to include agent\-level types, but the LLM policy slot then needs to produce an equilibrium selector, not merely a best\-response action\. Non\-stationary environments require either an explicit change\-point model inside\(T,Z\)\(T,Z\)or a forgetting mechanism on the filter\. We flag both as natural next steps\.

## IXConclusion

Large language model agents deployed as history\-conditioned text policies inherit a structural weakness that Chain\-of\-Thought prompting, longer context windows, and reflection loops do not address\. The weakness is that text accumulation is not belief maintenance\. Two histories whose raw texts differ can yield the same Bayesian posterior, and two histories whose posteriors agree can have arbitrarily different surface representations\. An LLM policy operating on the serialised history is acting on a representation strictly coarser than the belief MDP when the serialiser is lossy, and strictly finer than it when surface artifacts leak through\. Either way, the conditions of classical POMDP optimality are not met\.

We have developed an architectural response\. The Belief\-State Engine runs a Bayesian filter over a POMDP model as a module external to the LLM, and at each decision step presents the LLM with the posterior belief as its only decision\-time context\. Four independent axioms specify what any internal state must satisfy to qualify as belief\-consistent, and we have shown that the canonical posterior is the coarsest representation satisfying the structural axioms, that the Bayes filter is the unique update consistent with recursive belief maintenance, that policy and value coincide with the belief MDP under belief\-measurable policies, that observationally indistinguishable hypotheses are preserved by the filter, and that the LLM\-BSE composition is a sound Markov policy on the belief MDP\. The last of these is the precise sense in which the architecture converts an LLM text\-generator into a planning agent\.

The experimental program in[sectionVI](https://arxiv.org/html/2609.10036#S6)is designed to separate three questions: does an explicit belief help \(BSE\- augmented agent versus the four LLM baselines\); does the belief need to be probabilistic \(BSE\-augmented agent versus natural\-language belief tracker\); and does the benefit survive changes of backbone, of serialiser, of temperature, and of architectural detail \(the ten ablations and the open\-weights replication\)\. The paired\-seed structure, the Jensen\-Shannon decision\-consistency probe, and the pre\-registered metric list are chosen so that any headline finding from the experiments attaches to an architectural claim that is either confirmed or disconfirmed by a well\-defined test\. The full results and their analysis will be reported in[sectionVII](https://arxiv.org/html/2609.10036#S7)\.

Three broader implications follow if the experimental picture lines up with the theoretical one\. First, the LLM\-agent literature has a route by which to recover the optimality theory of sequential decision\-making under uncertainty, without retraining the LLM and without assuming that Chain\-of\-Thought reasoning can substitute for Bayesian conditioning\. Second, a large class of recurring failures in deployed LLM agents, including premature commitment, calibration collapse, and non\-Markovian policy drift, have a single structural remedy rather than a catalogue of prompt\-engineering fixes\. Third, the interface between LLMs and classical planning is lighter than one might expect: a thin external filter and a disciplined prompt are enough, provided the LLM is kept away from the raw history\.

Two lines of work open immediately\. The first is a quantitative theory of belief\-MDP value loss under particle and variational filter approximations, which is the path to scaling the architecture to latent spaces where the exact filter is not available\. The second is the interactive and multi\-agent extension, where the belief must also range over other agents’ policies and where the LLM is asked to select an equilibrium rather than a best response\. Both lines leave the axiomatic core intact\. What changes is the shape of the filter and the type of the policy slot, not the compositional principle the BSE is built on\.

We close with a design stance\. Deploying an LLM as a planner under partial observability is not, in the current state of the technology, a matter of asking the LLM to reason harder\. It is a matter of letting the LLM do what it is good at, which is selecting actions given a structured decision state, while giving the decision state itself to a module whose job is precisely that\. The Belief\-State Engine is a small commitment to that division of labour, and the theory and methodology we have presented are an attempt to make the commitment as explicit and as testable as possible\.

## References

- \[1\]S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. Cao, “ReAct: Synergizing reasoning and acting in language models,” in*International Conference on Learning Representations \(ICLR\)*, 2023, arXiv:2210\.03629\.
- \[2\]N\. Shinn, F\. Cassano, A\. Gopinath, K\. Narasimhan, and S\. Yao, “Reflexion: Language agents with verbal reinforcement learning,” in*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2023, arXiv:2303\.11366\.
- \[3\]S\. Yao, D\. Yu, J\. Zhao, I\. Shafran, T\. L\. Griffiths, Y\. Cao, and K\. Narasimhan, “Tree of thoughts: Deliberate problem solving with large language models,” in*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2023, arXiv:2305\.10601\.
- \[4\]G\. Wang, Y\. Xie, Y\. Jiang, A\. Mandlekar, C\. Xiao, Y\. Zhu, L\. Fan, and A\. Anandkumar, “Voyager: An open\-ended embodied agent with large language models,”*Transactions on Machine Learning Research \(TMLR\)*, 2024, arXiv:2305\.16291\.
- \[5\]J\. Yang, C\. E\. Jimenez, A\. Wettig, K\. Lieret, S\. Yao, K\. Narasimhan, and O\. Press, “SWE\-agent: Agent\-computer interfaces enable automated software engineering,” in*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2024, arXiv:2405\.15793\.
- \[6\]K\. Valmeekam, M\. Marquez, S\. Sreedharan, and S\. Kambhampati, “On the planning abilities of large language models: A critical investigation,” in*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2023, arXiv:2305\.15771\.
- \[7\]X\. Liu, H\. Yu, H\. Zhang, Y\. Xu, X\. Lei, H\. Lai, Y\. Gu, H\. Ding, K\. Men, K\. Yang, S\. Zhang, X\. Deng, A\. Zeng, Z\. Du, C\. Zhang, S\. Shen, T\. Zhang, Y\. Su, H\. Sun, M\. Huang, Y\. Dong, and J\. Tang, “AgentBench: Evaluating LLMs as agents,” in*International Conference on Learning Representations \(ICLR\)*, 2024, arXiv:2308\.03688\.
- \[8\]Z\. Xi, W\. Chen, X\. Guo, W\. He, Y\. Ding, B\. Hong, M\. Zhang, J\. Wang, S\. Jin, E\. Zhou*et al\.*, “The rise and potential of large language model based agents: A survey,”*Science China Information Sciences*, 2025, arXiv:2309\.07864\.
- \[9\]K\. J\. Åström, “Optimal control of Markov processes with incomplete state information,”*Journal of Mathematical Analysis and Applications*, vol\. 10, no\. 1, pp\. 174–205, 1965\.
- \[10\]R\. D\. Smallwood and E\. J\. Sondik, “The optimal control of partially observable Markov processes over a finite horizon,”*Operations Research*, vol\. 21, no\. 5, pp\. 1071–1088, 1973\.
- \[11\]M\. L\. Puterman,*Markov Decision Processes: Discrete Stochastic Dynamic Programming*\. New York, NY, USA: Wiley, 1994\.
- \[12\]L\. P\. Kaelbling, M\. L\. Littman, and A\. R\. Cassandra, “Planning and acting in partially observable stochastic domains,”*Artificial Intelligence*, vol\. 101, no\. 1–2, pp\. 99–134, 1998\.
- \[13\]E\. J\. Sondik, “The optimal control of partially observable Markov processes,” Ph\.D\. dissertation, Stanford University, 1971\.
- \[14\]C\. Striebel, “Sufficient statistics in the optimum control of stochastic systems,”*Journal of Mathematical Analysis and Applications*, vol\. 12, no\. 3, pp\. 576–592, 1965\.
- \[15\]C\. H\. Papadimitriou and J\. N\. Tsitsiklis, “The complexity of Markov decision processes,”*Mathematics of Operations Research*, vol\. 12, no\. 3, pp\. 441–450, 1987\.
- \[16\]J\. Pineau, G\. Gordon, and S\. Thrun, “Point\-based value iteration: An anytime algorithm for POMDPs,” in*Proc\. International Joint Conference on Artificial Intelligence \(IJCAI\)*, 2003\.
- \[17\]H\. Kurniawati, D\. Hsu, and W\. S\. Lee, “SARSOP: Efficient point\-based POMDP planning by approximating optimally reachable belief spaces,” in*Robotics: Science and Systems \(RSS\)*, 2008\.
- \[18\]M\. L\. Littman, A\. R\. Cassandra, and L\. P\. Kaelbling, “Learning policies for partially observable environments: Scaling up,” in*Proc\. International Conference on Machine Learning \(ICML\)*, 1995\.
- \[19\]D\. Silver and J\. Veness, “Monte\-Carlo planning in large POMDPs,” in*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2010\.
- \[20\]T\. R\. Sumers, S\. Yao, K\. Narasimhan, and T\. L\. Griffiths, “Cognitive architectures for language agents,”*Transactions on Machine Learning Research \(TMLR\)*, 2024, arXiv:2309\.02427\.
- \[21\]K\. Valmeekam, A\. Olmo, S\. Sreedharan, and S\. Kambhampati, “PlanBench: An extensible benchmark for evaluating large language models on planning and reasoning about change,” in*Advances in Neural Information Processing Systems \(NeurIPS\) Datasets and Benchmarks Track*, 2023, arXiv:2206\.10498\.
- \[22\]S\. Hao, Y\. Gu, H\. Ma, J\. Hong, Z\. Wang, D\. Wang, and Z\. Hu, “Reasoning with language model is planning with world model,” in*Proc\. Conference on Empirical Methods in Natural Language Processing \(EMNLP\)*, 2023, arXiv:2305\.14992\.
- \[23\]Y\. Du, O\. Watkins, Z\. Wang, C\. Colas, T\. Darrell, P\. Abbeel, A\. Gupta, and J\. Andreas, “Guiding pretraining in reinforcement learning with large language models,” in*Proc\. International Conference on Machine Learning \(ICML\)*, 2023, arXiv:2302\.06692\.
- \[24\]S\. M\. Xie, A\. Raghunathan, P\. Liang, and T\. Ma, “An explanation of in\-context learning as implicit Bayesian inference,” in*International Conference on Learning Representations \(ICLR\)*, 2022, arXiv:2111\.02080\.
- \[25\]S\. Kadavath, T\. Conerly, A\. Askell, T\. Henighan, D\. Drain, E\. Perez, N\. Schiefer, Z\. Hatfield\-Dodds, N\. DasSarma, E\. Tran\-Johnson*et al\.*, “Language models \(mostly\) know what they know,”*arXiv preprint arXiv:2207\.05221*, 2022\.
- \[26\]L\. Kuhn, Y\. Gal, and S\. Farquhar, “Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation,” in*International Conference on Learning Representations \(ICLR\)*, 2023, arXiv:2302\.09664\.
- \[27\]A\. N\. Angelopoulos and S\. Bates, “A gentle introduction to conformal prediction and distribution\-free uncertainty quantification,”*Foundations and Trends in Machine Learning*, vol\. 16, no\. 4, pp\. 494–591, 2023\.
- \[28\]A\. Chattopadhayay and D\. Halder, “An axiomatic framework for belief\-state representation in partially observable decision processes,” TechRxiv preprint, Feb\. 2026, authors’ earlier version of the present work; superseded by this preprint\.
- \[29\]C\. Phillips and L\. P\. Swiler, “A graph\-based system for network\-vulnerability analysis,” in*Proc\. New Security Paradigms Workshop \(NSPW\)*, 1998\.
- \[30\]A\. S\. Kechris,*Classical Descriptive Set Theory*, ser\. Graduate Texts in Mathematics\. New York, NY, USA: Springer\-Verlag, 1995, vol\. 156\.

## Appendix AProofs of Theorems in[sectionIV](https://arxiv.org/html/2609.10036#S4)

For convenience we repeat the canonical posterior recursion: withβ⁡\(∅\)=μ0\\beta\(\\varnothing\)=\\mu\_\{0\},

β⁡\(h⋅\(a,o\)\)​\(s′\)=Z⁡\(o∣s′,a\)​∑sT⁡\(s′∣s,a\)​β​\(h\)​\(s\)∑s′′Z⁡\(o∣s′′,a\)​∑sT⁡\(s′′∣s,a\)​β​\(h\)​\(s\)\.\\begin\{split\}\\beta\(h\\cdot\(a,o\)\)\(s^\{\\prime\}\)&=\\frac\{Z\(o\\mid s^\{\\prime\},a\)\\sum\_\{s\}T\(s^\{\\prime\}\\mid s,a\)\\,\\beta\(h\)\(s\)\}\{\\sum\_\{s^\{\\prime\\prime\}\}Z\(o\\mid s^\{\\prime\\prime\},a\)\\sum\_\{s\}T\(s^\{\\prime\\prime\}\\mid s,a\)\\,\\beta\(h\)\(s\)\}\.\\end\{split\}\(14\)We denote byUβU\_\{\\beta\}the operator onΔ⁡\(𝒮\)×𝒜×𝒪\\Delta\(\\mathcal\{S\}\)\\times\\mathcal\{A\}\\times\\mathcal\{O\}induced by \([14](https://arxiv.org/html/2609.10036#A1.E14)\)\. Throughout this appendix,t:=\|h\|t:=\|h\|, andℙ⁡\(⋅\)\\mathbb\{P\}\(\\cdot\)denotes the trajectory law induced byμ0\\mu\_\{0\},TT, andZZ\.

### A\-AProof of[theorem1](https://arxiv.org/html/2609.10036#Thmtheorem1)

We verify the three structural axioms in turn\.

*Axiom[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)\.*Settingx0=μ0x\_\{0\}=\\mu\_\{0\}andU=UβU=U\_\{\\beta\},β⁡\(∅\)=μ0=x0\\beta\(\\varnothing\)=\\mu\_\{0\}=x\_\{0\}by definition, andβ⁡\(h⋅\(a,o\)\)=Uβ​\(β⁡\(h\),a,o\)\\beta\(h\\cdot\(a,o\)\)=U\_\{\\beta\}\(\\beta\(h\),a,o\)by \([14](https://arxiv.org/html/2609.10036#A1.E14)\)\.

*Axiom[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)\.*By a standard computation,β⁡\(h\)​\(s\)=ℙ⁡\(St=s∣h,μ0\)\\beta\(h\)\(s\)=\\mathbb\{P\}\(S\_\{t\}\{=\}s\\mid h,\\mu\_\{0\}\), so the maph↦ℙ⁡\(St=s∣h\)h\\mapsto\\mathbb\{P\}\(S\_\{t\}\{=\}s\\mid h\)factors throughβ\\beta\. For the one\-step observation law, condition on the next latent state:

ℙ⁡\(Ot\+1=o∣h,a\)\\displaystyle\\mathbb\{P\}\(O\_\{t\+1\}\{=\}o\\mid h,a\)=∑s′∈𝒮Z⁡\(o∣s′,a\)​ℙ​\(St\+1=s′∣h,a\)\\displaystyle=\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}Z\(o\\mid s^\{\\prime\},a\)\\,\\mathbb\{P\}\(S\_\{t\+1\}\{=\}s^\{\\prime\}\\mid h,a\)=∑s′∈𝒮Z⁡\(o∣s′,a\)​∑s∈𝒮T⁡\(s′∣s,a\)​β​\(h\)​\(s\)\.\\displaystyle=\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}Z\(o\\mid s^\{\\prime\},a\)\\sum\_\{s\\in\\mathcal\{S\}\}T\(s^\{\\prime\}\\mid s,a\)\\,\\beta\(h\)\(s\)\.The right\-hand side depends onhhonly throughβ⁡\(h\)\\beta\(h\), so ifβ⁡\(h\)=β⁡\(h′\)\\beta\(h\)=\\beta\(h^\{\\prime\}\)thenℙ⁡\(Ot\+1=o∣h,a\)=ℙ⁡\(Ot′\+1=o∣h′,a\)\\mathbb\{P\}\(O\_\{t\+1\}\{=\}o\\mid h,a\)=\\mathbb\{P\}\(O\_\{t^\{\\prime\}\+1\}\{=\}o\\mid h^\{\\prime\},a\)as required\.

*Axiom[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)\.*By constructionβ⁡\(h\)\\beta\(h\)is a convex combination of elementary Bayesian posteriors; the denominator in \([14](https://arxiv.org/html/2609.10036#A1.E14)\) is the marginal observation probability and is strictly positive on the reachable set, soβ⁡\(h\)∈Δ⁡\(𝒮\)\\beta\(h\)\\in\\Delta\(\\mathcal\{S\}\)\. ∎

### A\-BProof of[theorem2](https://arxiv.org/html/2609.10036#Thmtheorem2)

Fixh,h′∈ℋh,h^\{\\prime\}\\in\\mathcal\{H\}withψ⁡\(h\)=ψ⁡\(h′\)\\psi\(h\)=\\psi\(h^\{\\prime\}\)\. By Axiom[A2](https://arxiv.org/html/2609.10036#Thmaxiom2),ℙ⁡\(St=s∣h\)=ℙ⁡\(St′=s∣h′\)\\mathbb\{P\}\(S\_\{t\}\{=\}s\\mid h\)=\\mathbb\{P\}\(S\_\{t^\{\\prime\}\}\{=\}s\\mid h^\{\\prime\}\)for everys∈𝒮s\\in\\mathcal\{S\}\. Sinceβ⁡\(h\)​\(s\)=ℙ⁡\(St=s∣h\)\\beta\(h\)\(s\)=\\mathbb\{P\}\(S\_\{t\}\{=\}s\\mid h\)andβ⁡\(h′\)​\(s\)=ℙ⁡\(St′=s∣h′\)\\beta\(h^\{\\prime\}\)\(s\)=\\mathbb\{P\}\(S\_\{t^\{\\prime\}\}\{=\}s\\mid h^\{\\prime\}\), we obtainβ⁡\(h\)=β⁡\(h′\)\\beta\(h\)=\\beta\(h^\{\\prime\}\)\. Henceβ\\betais constant on each fibreψ−1​\(\{x\}\)\\psi^\{\-1\}\(\\\{x\\\}\)ofψ\\psi, so it factors throughψ\\psi:

g⁡\(x\):=β⁡\(h\)for any​h​with​ψ​\(h\)=x,g\(x\):=\\beta\(h\)\\quad\\text\{for any \}h\\text\{ with \}\\psi\(h\)=x,is well defined onψ⁡\(ℋ\)\\psi\(\\mathcal\{H\}\)\. Since𝒳\\mathcal\{X\}is Polish andψ⁡\(ℋ\)\\psi\(\\mathcal\{H\}\)is analytic,ggextends to a measurable function on𝒳\\mathcal\{X\}by the measurable\-selection theorem\[[30](https://arxiv.org/html/2609.10036#bib.bib30), Thm\. 12\.13\]\. ∎

### A\-CProof of[corollary3](https://arxiv.org/html/2609.10036#Thmtheorem3)

Letψ\\psisatisfy Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)\.[theorem2](https://arxiv.org/html/2609.10036#Thmtheorem2)yields a measurableg:𝒳→Δ⁡\(𝒮\)g:\\mathcal\{X\}\\to\\Delta\(\\mathcal\{S\}\)withβ=g∘ψ\\beta=g\\circ\\psi\. Under[A3](https://arxiv.org/html/2609.10036#Thmaxiom3),ψ⁡\(h\)∈Δ⁡\(𝒮\)\\psi\(h\)\\in\\Delta\(\\mathcal\{S\}\)for everyhh\. Ifψ\\psiis itself pointwise equal to a Bayesian posterior on𝒮\\mathcal\{S\}, then for everyx∈ψ⁡\(ℋ\)x\\in\\psi\(\\mathcal\{H\}\),x=g⁡\(x\)x=g\(x\)andggis the identity onψ⁡\(ℋ\)\\psi\(\\mathcal\{H\}\); henceψ=β\\psi=\\betaon all ofℋ\\mathcal\{H\}\. ∎

### A\-DProof of[theorem4](https://arxiv.org/html/2609.10036#Thmtheorem4)

Letψ=β\\psi=\\betaand letUUsatisfy Axiom[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)forβ\\beta\. Take any\(b,a,o\)∈Δ⁡\(𝒮\)×𝒜×𝒪\(b,a,o\)\\in\\Delta\(\\mathcal\{S\}\)\\times\\mathcal\{A\}\\times\\mathcal\{O\}withb∈β⁡\(ℋ\)b\\in\\beta\(\\mathcal\{H\}\)andℙ⁡\(o∣b,a\)\>0\\mathbb\{P\}\(o\\mid b,a\)\>0\. Chooseh∈ℋh\\in\\mathcal\{H\}withβ⁡\(h\)=b\\beta\(h\)=b; such anhhexists by the assumptionb∈β⁡\(ℋ\)b\\in\\beta\(\\mathcal\{H\}\)\. Then

U⁡\(b,a,o\)=U⁡\(β⁡\(h\),a,o\)=β⁡\(h⋅\(a,o\)\)=Uβ​\(b,a,o\),U\(b,a,o\)=U\(\\beta\(h\),a,o\)=\\beta\(h\\cdot\(a,o\)\)=U\_\{\\beta\}\(b,a,o\),where the middle equality uses Axiom[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)forUUand the final equality is[definition1](https://arxiv.org/html/2609.10036#Thmdefinition1)\. IfUUis continuous onΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\)in its first argument, thenUUandUβU\_\{\\beta\}agree on the reachable set and both are continuous, so they agree on its closure, which is all ofΔ⁡\(𝒮\)\\Delta\(\\mathcal\{S\}\)\. ∎

### A\-EProof of[theorem5](https://arxiv.org/html/2609.10036#Thmtheorem5)

By Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)there exists measurableπ~\\tilde\{\\pi\}withπ\(⋅∣h\)=π~\(⋅∣ψ\(h\)\)\\pi\(\\cdot\\mid h\)=\\tilde\{\\pi\}\(\\cdot\\mid\\psi\(h\)\)for everyhh\. Ifψ⁡\(h\)=ψ⁡\(h′\)\\psi\(h\)=\\psi\(h^\{\\prime\}\), thenπ\(⋅∣h\)=π~\(⋅∣ψ\(h\)\)=π~\(⋅∣ψ\(h′\)\)=π\(⋅∣h′\)\\pi\(\\cdot\\mid h\)=\\tilde\{\\pi\}\(\\cdot\\mid\\psi\(h\)\)=\\tilde\{\\pi\}\(\\cdot\\mid\\psi\(h^\{\\prime\}\)\)=\\pi\(\\cdot\\mid h^\{\\prime\}\)\. ∎

### A\-FProof of[theorem6](https://arxiv.org/html/2609.10036#Thmtheorem6)

We prove the finite\-horizon version by induction on the horizonTT\. The infinite\-horizon discounted case then follows by a standard contraction\-mapping argument on the belief MDP\[[11](https://arxiv.org/html/2609.10036#bib.bib11), Ch\. 6\]\.

*Base case \(T=0T=0\)\.*No future reward is collected, so

V0,ℋ⋆​\(h\)=max⁡∑s∈𝒮a∈𝒜⁡β⁡\(h\)​\(s\)​R​\(s,a\)=V0,Δ⋆​\(β⁡\(h\)\)\.V\_\{0,\\mathcal\{H\}\}^\{\\star\}\(h\)=\\max\_\{a\\in\\mathcal\{A\}\}\\sum\_\{s\\in\\mathcal\{S\}\}\\beta\(h\)\(s\)\\,R\(s,a\)=V\_\{0,\\Delta\}^\{\\star\}\(\\beta\(h\)\)\.
*Inductive step\.*SupposeVT−1,ℋ⋆​\(h\)=VT−1,Δ⋆​\(β⁡\(h\)\)V\_\{T\-1,\\mathcal\{H\}\}^\{\\star\}\(h\)=V\_\{T\-1,\\Delta\}^\{\\star\}\(\\beta\(h\)\)for everyhh\. Then

VT,ℋ⋆​\(h\)=\\displaystyle V\_\{T,\\mathcal\{H\}\}^\{\\star\}\(h\)=\{\}maxa∈𝒜\[∑s∈𝒮β\(h\)\(s\)R\(s,a\)\\displaystyle\\max\_\{a\\in\\mathcal\{A\}\}\\Big\[\\sum\_\{s\\in\\mathcal\{S\}\}\\beta\(h\)\(s\)\\,R\(s,a\)\+γ∑o∈𝒪ℙ\(o∣h,a\)VT−1,ℋ⋆\(h⋅\(a,o\)\)\]\.\\displaystyle\\quad\+\\gamma\\sum\_\{o\\in\\mathcal\{O\}\}\\mathbb\{P\}\(o\\mid h,a\)\\,V\_\{T\-1,\\mathcal\{H\}\}^\{\\star\}\(h\\cdot\(a,o\)\)\\Big\]\.By Axiom[A2](https://arxiv.org/html/2609.10036#Thmaxiom2),ℙ⁡\(o∣h,a\)=ℙ⁡\(o∣β⁡\(h\),a\)\\mathbb\{P\}\(o\\mid h,a\)=\\mathbb\{P\}\(o\\mid\\beta\(h\),a\)\. By[definition1](https://arxiv.org/html/2609.10036#Thmdefinition1),β⁡\(h⋅\(a,o\)\)=Uβ​\(β⁡\(h\),a,o\)\\beta\(h\\cdot\(a,o\)\)=U\_\{\\beta\}\(\\beta\(h\),a,o\)\. By the induction hypothesis,VT−1,ℋ⋆​\(h⋅\(a,o\)\)=VT−1,Δ⋆​\(Uβ​\(β⁡\(h\),a,o\)\)V\_\{T\-1,\\mathcal\{H\}\}^\{\\star\}\(h\\cdot\(a,o\)\)=V\_\{T\-1,\\Delta\}^\{\\star\}\(U\_\{\\beta\}\(\\beta\(h\),a,o\)\)\. Substituting these three equalities,

VT,ℋ⋆​\(h\)=\\displaystyle V\_\{T,\\mathcal\{H\}\}^\{\\star\}\(h\)=\{\}maxa∈𝒜\[∑s∈𝒮β\(h\)\(s\)R\(s,a\)\\displaystyle\\max\_\{a\\in\\mathcal\{A\}\}\\Big\[\\sum\_\{s\\in\\mathcal\{S\}\}\\beta\(h\)\(s\)\\,R\(s,a\)\+γ∑o∈𝒪ℙ\(o∣β\(h\),a\)VT−1,Δ⋆\(Uβ\(β\(h\),a,o\)\)\]\\displaystyle\\quad\+\\gamma\\sum\_\{o\\in\\mathcal\{O\}\}\\mathbb\{P\}\(o\\mid\\beta\(h\),a\)\\,V\_\{T\-1,\\Delta\}^\{\\star\}\(U\_\{\\beta\}\(\\beta\(h\),a,o\)\)\\Big\]=\\displaystyle=\{\}VT,Δ⋆​\(β⁡\(h\)\),\\displaystyle V\_\{T,\\Delta\}^\{\\star\}\(\\beta\(h\)\),which is the Bellman recursion of the belief MDP\. The optimal history\-policy is obtained by applying the same argument to the greedy policy of the belief MDP\. ∎

### A\-GProof of[theorem7](https://arxiv.org/html/2609.10036#Thmtheorem7)

Lets∼s′s\\sim s^\{\\prime\}and leth⋅\(a,o\)h\\cdot\(a,o\)be any single\-step extension of a historyhh\. From \([14](https://arxiv.org/html/2609.10036#A1.E14)\),

β​\(h⋅\(a,o\)\)​\(s\)β⁡\(h⋅\(a,o\)\)​\(s′\)\\displaystyle\\frac\{\\beta\(h\\cdot\(a,o\)\)\(s\)\}\{\\beta\(h\\cdot\(a,o\)\)\(s^\{\\prime\}\)\}=Z⁡\(o∣s,a\)Z⁡\(o∣s′,a\)⏟=1​by \(i\)\\displaystyle=\\underbrace\{\\frac\{Z\(o\\mid s,a\)\}\{Z\(o\\mid s^\{\\prime\},a\)\}\}\_\{=1\\text\{ by \(i\)\}\}⋅∑s~T⁡\(s∣s~,a\)​β​\(h\)​\(s~\)∑s~T⁡\(s′∣s~,a\)​β​\(h\)​\(s~\)⏟=1​by \(ii\)=1\.\\displaystyle\\quad\\cdot\\underbrace\{\\frac\{\\sum\_\{\\tilde\{s\}\}T\(s\\mid\\tilde\{s\},a\)\\,\\beta\(h\)\(\\tilde\{s\}\)\}\{\\sum\_\{\\tilde\{s\}\}T\(s^\{\\prime\}\\mid\\tilde\{s\},a\)\\,\\beta\(h\)\(\\tilde\{s\}\)\}\}\_\{=1\\text\{ by \(ii\)\}\}=1\.Hence a single update preserves the equalityβ⁡\(⋅\)​\(s\)=β⁡\(⋅\)​\(s′\)\\beta\(\\cdot\)\(s\)=\\beta\(\\cdot\)\(s^\{\\prime\}\)\. Induction on history length, with base caseβ⁡\(∅\)=μ0\\beta\(\\varnothing\)=\\mu\_\{0\}, completes the proof\. ∎

### A\-HProof of[corollary8](https://arxiv.org/html/2609.10036#Thmtheorem8)

Immediate from[theorem7](https://arxiv.org/html/2609.10036#Thmtheorem7)withμ0​\(s\)=μ0​\(s′\)\\mu\_\{0\}\(s\)=\\mu\_\{0\}\(s^\{\\prime\}\)as the base case of the induction\. ∎

### A\-IProof of[theorem9](https://arxiv.org/html/2609.10036#Thmtheorem9)

*Axioms\.*Axiom[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)holds by the choiceU=UβU=U\_\{\\beta\}withx0=μ0x\_\{0\}=\\mu\_\{0\}\. Axiom[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)is[theorem1](https://arxiv.org/html/2609.10036#Thmtheorem1)applied toβ\\beta\. Axiom[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)holds becausebt=β⁡\(ht\)∈Δ⁡\(𝒮\)b\_\{t\}=\\beta\(h\_\{t\}\)\\in\\Delta\(\\mathcal\{S\}\)by construction\. Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)holds by hypothesis:πLLM\\pi\_\{\\textsc\{LLM\}\}is a measurable function of the belief\.

*Markovianity of\(bt,at\)\(b\_\{t\},a\_\{t\}\)\.*Conditional onbt=β⁡\(ht\)b\_\{t\}=\\beta\(h\_\{t\}\)andat=aa\_\{t\}=a, Axiom[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)givesℙ⁡\(o∣ht,a\)=ℙ⁡\(o∣bt,a\)\\mathbb\{P\}\(o\\mid h\_\{t\},a\)=\\mathbb\{P\}\(o\\mid b\_\{t\},a\)\. The next belief is deterministic given\(bt,at,ot\+1\)\(b\_\{t\},a\_\{t\},o\_\{t\+1\}\):bt\+1=Uβ​\(bt,at,ot\+1\)b\_\{t\+1\}=U\_\{\\beta\}\(b\_\{t\},a\_\{t\},o\_\{t\+1\}\)\. The next action is drawn fromπLLM\(⋅∣bt\+1\)\\pi\_\{\\textsc\{LLM\}\}\(\\cdot\\mid b\_\{t\+1\}\)by Axiom[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)\. Combining these,

ℙ\(bt\+1=b′,at\+1=a′∣bt=b,at=a\)\\displaystyle\\mathbb\{P\}\(b\_\{t\+1\}\{=\}b^\{\\prime\},a\_\{t\+1\}\{=\}a^\{\\prime\}\\mid b\_\{t\}\{=\}b,a\_\{t\}\{=\}a\)=∑o∈𝒪\[b′=Uβ\(b,a,o\)\]ℙ\(o∣b,a\)πLLM\(a′∣b′\),\\displaystyle\\quad=\\sum\_\{o\\in\\mathcal\{O\}\}\\mathbf\{1\}\\\!\\left\[b^\{\\prime\}=U\_\{\\beta\}\(b,a,o\)\\right\]\\mathbb\{P\}\(o\\mid b,a\)\\,\\pi\_\{\\textsc\{LLM\}\}\(a^\{\\prime\}\\mid b^\{\\prime\}\),which is \([12](https://arxiv.org/html/2609.10036#S4.E12)\)\.

*Value coincidence\.*Apply[theorem6](https://arxiv.org/html/2609.10036#Thmtheorem6)withπ~=πLLM\\tilde\{\\pi\}=\\pi\_\{\\textsc\{LLM\}\}in the role of the belief\-measurable policy\. The value of the history\-policyπℋ\(⋅∣h\):=πLLM\(⋅∣β\(h\)\)\\pi\_\{\\mathcal\{H\}\}\(\\cdot\\mid h\):=\\pi\_\{\\textsc\{LLM\}\}\(\\cdot\\mid\\beta\(h\)\)equals the value ofπLLM\\pi\_\{\\textsc\{LLM\}\}on the belief MDP\. ∎

## Appendix BIndependence of Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)

###### Proposition 10\(Independence of the axiom set\)\.

Axioms[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)are mutually independent\. For each axiomA​i\\mathrm\{A\}ithere exists a representation that satisfies the remaining three axioms but notA​i\\mathrm\{A\}i\.

###### Proof\.

We exhibit four explicit counter\-models\.

*Not[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)\.*Letψ⁡\(h\):=\|h\|\\psi\(h\):=\|h\|, the history length, valued inℕ⊂ℝ\\mathbb\{N\}\\subset\\mathbb\{R\}\. The composite\(ψ,π~∘ψ\)\(\\psi,\\tilde\{\\pi\}\\circ\\psi\)cannot be equipped with a fixed operatorU:ℕ×𝒜×𝒪→ℕU:\\mathbb\{N\}\\times\\mathcal\{A\}\\times\\mathcal\{O\}\\to\\mathbb\{N\}that reproduces the joint evolution of\(St,Ot\)\(S\_\{t\},O\_\{t\}\)throughψ\\psialone, because\|h\|\|h\|carries no information about either\. Sufficiency[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)therefore fails too in this trivial model\. A more instructive counter\-model that fails only[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)isψ⁡\(h\):=h\\psi\(h\):=h, the raw history, with𝒳=ℋ\\mathcal\{X\}=\\mathcal\{H\}\. This is trivially sufficient in the measure\-theoretic sense, and any policy can be written asπ​\(h\)=π~​\(ψ​\(h\)\)\\pi\(h\)=\\tilde\{\\pi\}\(\\psi\(h\)\)withπ~=π\\tilde\{\\pi\}=\\pi, but no single operatorU:𝒳×𝒜×𝒪→𝒳U:\\mathcal\{X\}\\times\\mathcal\{A\}\\times\\mathcal\{O\}\\to\\mathcal\{X\}of constant signature acts as the update, because the natural update takes\(h,a,o\)↦h⋅\(a,o\)\(h,a,o\)\\mapsto h\\cdot\(a,o\), whose codomainℋt\+1\\mathcal\{H\}\_\{t\+1\}strictly extendsℋt\\mathcal\{H\}\_\{t\}\. Recastingψ\\psito live in⋃tℋt\\bigcup\_\{t\}\\mathcal\{H\}\_\{t\}repairs the signature but still fails the fixed\-domain requirement: the state at timettis confined toℋt\\mathcal\{H\}\_\{t\}and cannot be updated from an arbitrary element of𝒳\\mathcal\{X\}\.

*Not[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)\.*Takeψ⁡\(h\)≡μ0\\psi\(h\)\\equiv\\mu\_\{0\}, the constant representation that ignores all observations\. ThenU=idU=\\mathrm\{id\}satisfies[A1](https://arxiv.org/html/2609.10036#Thmaxiom1);ψ∈Δ⁡\(𝒮\)\\psi\\in\\Delta\(\\mathcal\{S\}\)satisfies[A3](https://arxiv.org/html/2609.10036#Thmaxiom3); anyπ~:Δ⁡\(𝒮\)→Δ⁡\(𝒜\)\\tilde\{\\pi\}:\\Delta\(\\mathcal\{S\}\)\\to\\Delta\(\\mathcal\{A\}\)satisfies[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)\. Yetψ\\psiis not sufficient whenever observations carry information aboutStS\_\{t\}, so[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)fails\.

*Not[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)\.*Takeψ⁡\(h\):=1000⋅β⁡\(h\)\\psi\(h\):=1000\\cdot\\beta\(h\), a homeomorphic re\-encoding ofβ\\betainto\[0,1000\]\|𝒮\|\[0,1000\]^\{\|\\mathcal\{S\}\|\}\. ConjugatingUβU\_\{\\beta\}by the re\-encoding yields a valid update operatorU⁡\(x,a,o\):=1000⋅Uβ​\(x/1000,a,o\)U\(x,a,o\):=1000\\cdot U\_\{\\beta\}\(x/1000,a,o\)satisfying[A1](https://arxiv.org/html/2609.10036#Thmaxiom1); sufficiency[A2](https://arxiv.org/html/2609.10036#Thmaxiom2)is preserved becauseψ\\psiis a bijection on the reachable set;π~\(⋅∣x\):=π⋆\(⋅∣x/1000\)\\tilde\{\\pi\}\(\\cdot\\mid x\):=\\pi^\{\\star\}\(\\cdot\\mid x/1000\)recovers[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)\. Butψ⁡\(h\)∉Δ⁡\(𝒮\)\\psi\(h\)\\notin\\Delta\(\\mathcal\{S\}\), so[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)fails\.

*Not[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)\.*Letψ=β\\psi=\\beta, so that[A1](https://arxiv.org/html/2609.10036#Thmaxiom1)–[A3](https://arxiv.org/html/2609.10036#Thmaxiom3)hold by[theorem1](https://arxiv.org/html/2609.10036#Thmtheorem1)\. Define a policy that depends on the parity of\|h\|\|h\|as well asβ⁡\(h\)\\beta\(h\):

π⁡\(a∣h\):=\{π~even​\(a∣β​\(h\)\)if​\|h\|​even,π~odd​\(a∣β​\(h\)\)if​\|h\|​odd,\\pi\(a\\mid h\):=\\begin\{cases\}\\tilde\{\\pi\}\_\{\\text\{even\}\}\(a\\mid\\beta\(h\)\)&\\text\{if \}\|h\|\\text\{ even\},\\\\ \\tilde\{\\pi\}\_\{\\text\{odd\}\}\(a\\mid\\beta\(h\)\)&\\text\{if \}\|h\|\\text\{ odd\},\\end\{cases\}withπ~even≠π~odd\\tilde\{\\pi\}\_\{\\text\{even\}\}\\neq\\tilde\{\\pi\}\_\{\\text\{odd\}\}\. Two historiesh,h′h,h^\{\\prime\}with the same belief but different length parities yieldπ\(⋅∣h\)≠π\(⋅∣h′\)\\pi\(\\cdot\\mid h\)\\neq\\pi\(\\cdot\\mid h^\{\\prime\}\), so no single measurableπ~:Δ⁡\(𝒮\)→Δ⁡\(𝒜\)\\tilde\{\\pi\}:\\Delta\(\\mathcal\{S\}\)\\to\\Delta\(\\mathcal\{A\}\)satisfies[A4](https://arxiv.org/html/2609.10036#Thmaxiom4)\. ∎

## Appendix CEnvironment Specifications

This appendix gives the exact transition, observation, and reward parameters implemented in the released environment code \(tiger\_pomdp/environment\.pyandred\_team\_graph/environment\.py\), matching the summary in[sectionVI\-A](https://arxiv.org/html/2609.10036#S6.SS1)\.

### C\-ATiger POMDP

𝒮=\{left,right\}\\mathcal\{S\}=\\\{\\text\{left\},\\text\{right\}\\\},𝒜=\{listen,open\-left,open\-right\}\\mathcal\{A\}=\\\{\\text\{listen\},\\text\{open\-left\},\\text\{open\-right\}\\\},𝒪=\{hear\-left,hear\-right\}\\mathcal\{O\}=\\\{\\text\{hear\-left\},\\text\{hear\-right\}\\\},μ0=\(0\.5,0\.5\)\\mu\_\{0\}=\(0\.5,0\.5\),γ=0\.95\\gamma=0\.95,Tmax=20T\_\{\\max\}=20\.

T\(⋅∣⋅,listen\)\\displaystyle T\(\\cdot\\mid\\cdot,\\text\{listen\}\)=I2,\\displaystyle=I\_\{2\},T\(⋅∣⋅,open\-left\)=T\(⋅∣⋅,open\-right\)\\displaystyle T\(\\cdot\\mid\\cdot,\\text\{open\-left\}\)=T\(\\cdot\\mid\\cdot,\\text\{open\-right\}\)=\[0\.50\.50\.50\.5\],\\displaystyle=\\begin\{bmatrix\}0\.5&0\.5\\\\ 0\.5&0\.5\\end\{bmatrix\},Z\(⋅∣⋅,listen\)\\displaystyle Z\(\\cdot\\mid\\cdot,\\text\{listen\}\)=\[0\.850\.150\.150\.85\],\\displaystyle=\\begin\{bmatrix\}0\.85&0\.15\\\\ 0\.15&0\.85\\end\{bmatrix\},Z\(⋅∣⋅,open\-left\)=Z\(⋅∣⋅,open\-right\)\\displaystyle Z\(\\cdot\\mid\\cdot,\\text\{open\-left\}\)=Z\(\\cdot\\mid\\cdot,\\text\{open\-right\}\)=\[0\.50\.50\.50\.5\]\.\\displaystyle=\\begin\{bmatrix\}0\.5&0\.5\\\\ 0\.5&0\.5\\end\{bmatrix\}\.Rows/columns are ordered \(left, right\)\. RewardR⁡\(left,⋅\)=\(−1,−100,\+10\)R\(\\text\{left\},\\cdot\)=\(\-1,\-100,\+10\)andR⁡\(right,⋅\)=\(−1,\+10,−100\)R\(\\text\{right\},\\cdot\)=\(\-1,\+10,\-100\)over \(listen, open\-left, open\-right\)\.

### C\-BRed\-Team Attack Graph \(K=6K=6\)

𝒮=\{0,1\}6\\mathcal\{S\}=\\\{0,1\\\}^\{6\}\(\|𝒮\|=64\|\\mathcal\{S\}\|=64\), one binary \(*vulnerable*/*hardened*\) latent variable per node\.𝒜=\{scan\(i\),exploit\(i\):i∈\{0,…,5\}\}∪\{wait\}\\mathcal\{A\}=\\\{\\text\{scan\}\(i\),\\text\{exploit\}\(i\):i\\in\\\{0,\\dots,5\\\}\\\}\\cup\\\{\\text\{wait\}\\\}; thepatchaction family exists in the model definition but is excluded from the action menu presented to every method, because its transition dynamics are an unimplemented placeholder in the released environment \([sectionVII\-D](https://arxiv.org/html/2609.10036#S7.SS4)\)\.𝒪=\{0,1\}\\mathcal\{O\}=\\\{0,1\\\}\(scan result\),γ=0\.95\\gamma=0\.95,Tmax=30T\_\{\\max\}=30,μ0=\\mu\_\{0\}=uniform over𝒮\\mathcal\{S\}\.

*Observation model\.*scan​\(i\)\\text\{scan\}\(i\)yieldsZ​\(1∣state,scan​\(i\)\)=0\.85Z\(1\\mid\\text\{state\},\\text\{scan\}\(i\)\)=0\.85if nodeiiis vulnerable and0\.100\.10if hardened \(i\.e\. false\-negative rateβ=0\.15\\beta=0\.15, false\-positive rateα=0\.10\\alpha=0\.10\); every other action yields an uninformative observation,Z\(o∣⋅,a\)=0\.5Z\(o\\mid\\cdot,a\)=0\.5fora≠scan​\(⋅\)a\\neq\\text\{scan\}\(\\cdot\)\.

*Transition model\.*As implemented,T\(⋅∣s,a\)=𝟏\[s\]T\(\\cdot\\mid s,a\)=\\mathbf\{1\}\[s\]\(the identity\) for*every*actionaa, includingexploit: node hardening bypatchand state change onexploitare unimplemented placeholders \(environment\.pycontains aTODOto this effect\)\. A node\-dependency topology for lateral movement is declared but not wired into the transition kernel:dependencies = \{0: \[\], 1: \[\], 2: \[0\], 3: \[0,1\], 4: \[2,3\], 5: \[2,3\]\}, encoding an intended prerequisite structure \(nodes 2 and 3 depend on node 0/1 being compromised first, nodes 4 and 5 depend on both 2 and 3\) that the current release does not yet enforce\. Node vulnerability is instead drawn i\.i\.d\. per episode\. This is the reasonAB1\(drop prediction step\) shows only a near\-null effect on this environment \([sectionVII\-C](https://arxiv.org/html/2609.10036#S7.SS3)\): the operation it removes is already a no\-op under the identity kernel\.

*Reward\.*R⁡\(scan\)=−0\.5R\(\\text\{scan\}\)=\-0\.5,R⁡\(exploit\-success\)=\+20R\(\\text\{exploit\-success\}\)=\+20,R⁡\(exploit\-fail\)=−5R\(\\text\{exploit\-fail\}\)=\-5,R⁡\(wait\)=−0\.1R\(\\text\{wait\}\)=\-0\.1; a repeat exploit on an already\-compromised node pays00\(no reward farming\)\. These match[sectionVI\-A](https://arxiv.org/html/2609.10036#S6.SS1)except thatR⁡\(patch\)R\(\\text\{patch\}\)is not applicable, sincepatchis excluded from the action menu\.

## Appendix DPrompt Templates

This appendix reproduces the exact system and user prompts issued to the LLM by the evaluation scripts \(tiger\_pomdp/run\_full\_eval\.pyandred\_team\_graph/run\_full\_eval\.py\), for the three methods evaluated in[sectionVII\-A](https://arxiv.org/html/2609.10036#S7.SS1)\. All three methods within an environment share the same system prompt, temperature, and parser \([sectionVI\-B](https://arxiv.org/html/2609.10036#S6.SS2)\); only the state representation in the user prompt differs\.\{…\}denotes a value substituted at run time\.

### D\-ATiger POMDP

*System prompt\.*

```
Select the action that maximizes the expected
immediate reward given the information provided
below. Break ties uniformly. Output your
reasoning, then a final line strictly formatted
as ’ACTION: <action>’.
```

*Reactive user prompt\.*

```
DOMAIN: Tiger POMDP
GOAL: Choose the door without the tiger.
REWARDS: +10 for treasure, -100 for tiger, -1 for
listening.
AVAILABLE ACTIONS: listen, open-left, open-right

LATEST SENSOR OBSERVATION: {hear-left|hear-right}
```

*BSEuser prompt\.*

```
DOMAIN: Tiger POMDP
GOAL: Choose the door with treasure while avoiding
the tiger.
REWARDS: +10 for treasure, -100 for tiger, -1 for
listening.
AVAILABLE ACTIONS: listen, open-left, open-right

CURRENT BELIEF POSTERIOR:
- tiger-left:  {b(left):.4f}
- tiger-right: {b(right):.4f}
```

*NL\-Tracker user prompt\.*

```
DOMAIN: Tiger POMDP
GOAL: Choose the door with treasure while avoiding
the tiger.
REWARDS: +10 for treasure, -100 for tiger, -1 for
listening.
AVAILABLE ACTIONS: listen, open-left, open-right

YOUR PREVIOUS BELIEF SUMMARY:
{belief text from previous step}

LATEST ACTION-OBSERVATION: action={action},
observation={observation}

INSTRUCTION: First write one line starting with
’BELIEF:’ that states your updated belief in
natural language, including your best estimate of
the probability the tiger is on the left vs. the
right (e.g., ’BELIEF: ~80% left, ~20% right, based
on ...’). Then output a final line strictly
formatted as ’ACTION: <action>’.
```

### D\-BRed\-Team Attack Graph

*System prompt\.*

```
Select the action that maximizes your expected
discounted return over the remaining steps of the
episode, not just the immediate reward -- scanning
now can be worth a short-term cost if it avoids a
larger expected loss later. Use the information
provided below. Break ties uniformly. Output your
reasoning, then a final line strictly formatted as
’ACTION: <action>’.
```

*Reactive user prompt\.*

```
DOMAIN: K=6 Red-Team Attack Graph
GOAL: Discover vulnerable entry points and execute
successful exploits.
REWARDS: +20 for successful exploit, -5 for failed
exploit, -0.5 for scan, -0.1 for wait.
STEPS REMAINING: {steps_remaining}
AVAILABLE ACTIONS: scan_0, ..., scan_5, exploit_0,
..., exploit_5, wait

{Already compromised nodes, if any.}

LATEST SCAN OBSERVATION: Scanned node {i},
result={0|1} (1=flagged vulnerable, 0=clean).
```

*BSEuser prompt\.*Identical header/reward/action lines to the Reactive prompt above, replacing the observation line with:

```
CURRENT MARGINAL PROBABILITY OF EACH NODE BEING
VULNERABLE:
- Node 0: {p_0:.4f}
...
- Node 5: {p_5:.4f}
```

wherepi=∑s:si=1b\(s\)p\_\{i\}=\\sum\_\{s:s\_\{i\}=1\}b\(s\)is the per\-node marginal of the full 64\-state posterior\.

*NL\-Tracker user prompt\.*Identical header/reward/action lines, with the previous free\-text belief and an instruction analogous to the Tiger case, adapted to per\-node probabilities:

```
YOUR PREVIOUS BELIEF SUMMARY:
{belief text from previous step}

LATEST SCAN OBSERVATION: {as above}

INSTRUCTION: First write one line starting with
’BELIEF:’ that states, for each of the 6 nodes,
your estimated probability it is vulnerable (e.g.
’BELIEF: Node 0: 70%, Node 1: 20%, ...’). Then
output a final line strictly formatted as
’ACTION: <action>’.
```

## Appendix EAdditional Experimental Details

This appendix records the configuration actually used to produce the numbers in[sectionVII](https://arxiv.org/html/2609.10036#S7), as distinct from the full designed protocol of[sectionVI](https://arxiv.org/html/2609.10036#S6)\([sectionVII\-A](https://arxiv.org/html/2609.10036#S7.SS1)explains the gap between the two\)\.

*Model and decoding\.*gpt\-4ovia the OpenAI API,τ=0\.3\\tau=0\.3for the main comparisons and ablationsAB1/AB2,τ=1\.0\\tau=1\.0forAB9\. On a malformed or unparseable completion, the harness retries once atτ=0\.0\\tau=0\.0before falling back to a fixed default action \(listenfor Tiger,waitfor the attack graph\); fallback calls are logged and counted in the reported abstention rate but not excluded from the returns\.

*Sample sizes and concurrency\.*Main comparisons useN=40N=40paired episode seeds \(0,…,390,\\dots,39\) per environment instance; ablations useN=25N=25seeds \(0,…,240,\\dots,24\); a single LLM\-sampling seed per episode in both cases\. Episodes are run concurrently with a thread pool of 5 workers to keep live\-API wall\-clock time tractable\.

*Bootstrap\.*Percentile bootstrap on the mean, 2,000 resamples, fixed RNG seed 0\. This is fewer than the 10,000 resamples specified for the full protocol in[sectionVI\-C](https://arxiv.org/html/2609.10036#S6.SS3), reduced for run time given the smallerNN; confidence intervals atN=40N=40are wide regardless of resample count, so this reduction has negligible effect on the reported intervals\.

*Decision consistency\.*Rather than the 200 pre\-selected belief\-equivalent pairs withK=32K=32resamples per pair specified in[sectionVI\-C](https://arxiv.org/html/2609.10036#S6.SS3), the reported numbers use an opportunistic, reduced version: up to 10 \(Tiger\) or 8 \(attack graph\) belief\-collision groups mined from each method’s own main\-run trajectories, resampledK=5K=5times each\. Tiger yielded zero qualifying groups atN=40N=40\(reported as not measured\); the attack graph yielded 24 pairs\.

*Parser\.*An exact\-match parser scans the completion for a line beginningACTION:and accepts it only if the remainder matches one of the environment’s action names verbatim\.

*Per\-episode compute\.*Representative values from the logged main\-comparison runs \(logs/2026\-09\-02/\): on Tiger, mean latency per episode is 4\.1 s \(Reactive\), 9\.4 s \(BSE\), 0\.9 s \(NL\-Tracker\); on the attack graph, 111\.6 s \(Reactive\), 140\.5 s \(BSE\), 56\.6 s \(NL\-Tracker\)\. The larger gap on the attack graph reflects its longer horizon \(T=30T=30vs\.T=20T=20\) and larger average token count per call\.

*Not implemented in this evaluation round\.*Chain\-of\-Thought, ReAct, QMDP, and POMCP baselines; the open\-weights replication; and ablationsAB3–AB8andAB10\. No hyperparameters \(POMCP simulation count, UCB1 exploration constant, particle\-filter size, etc\.\) were therefore tuned or run for this round; the values quoted in[sectionVI\-B](https://arxiv.org/html/2609.10036#S6.SS2)describe the intended configuration for a future full run, not a completed one\.

*Raw logs\.*Per\-run JSON summaries and per\-call logs are atlogs/2026\-09\-02/\{tiger,attack\}\_\{full,ablations\}\_eval\_results\.json, produced by the following scripts, released with the code accompanying this preprint:

- •tiger\_pomdp/run\_full\_eval\.py
- •tiger\_pomdp/run\_ablations\_eval\.py
- •red\_team\_graph/run\_full\_eval\.py
- •red\_team\_graph/run\_ablations\_eval\.py