Active Inference as Context Acquisition for AI Agents

# Active Inference as Context Acquisition for AI Agents
Source: [https://arxiv.org/html/2608.19202](https://arxiv.org/html/2608.19202)
\\nameSanchayan Dutta\\emaildutta@ucdavis\.edu \\addrDepartment of Mathematics, University of California, Davis \\nameSai Niranjan Ramachandran\\emailsainiranjan\.ramachandran@tum\.de \\addrTechnical University of Munich, Garching, Germany \\nameSuvrit Sra\\emails\.sra@tum\.de \\addrTechnical University of Munich, Garching, Germany

###### Abstract

Interactive AI agents must acquire the right context as efficiently as possible\. When a user omits a constraint, preference, file, or task variable, an agent can proceed with a default assumption or spend tokens on a clarifying question, retrieval call, tool call, or prompt trial\. We formulate this tradeoff as active inference for context acquisition\. An inner inference step updates beliefs over a latent task state, and an outer decision selects the next context action, task action, or stop action to minimize expected free energy under cost\. In deterministic settings, the epistemic term reduces to expected information gain, optionally normalized by token cost\. We instantiate the framework in Optimal Question Asking \(OQA\), with exact posteriors and a dynamic programming oracle, and benchmark frontier language models on binary and multiway categorical tasks from 25 to 300 candidates\. We also study clarification before generation and automated prompt optimization under token budgets\. The formulation is model\-agnostic and views active inference as a design principle for the context\-acquisition layer of AI agents\.

## 1Introduction

Users of AI systems rarely specify everything up front\. A constraint may be omitted or a preference left implicit\. Faced with such inputs, the system can commit early and risk being wrong, or it can acquire more context first\. The context action might be a clarifying question, retrieval call, tool call, prompt evaluation, or visual inspection\. Each such action has a price\. It costs tokens, adds latency, and can require effort from a user or environment\.

We study this tradeoff using active inference\. Letxxbe the latent task state, such as intent, target, preference, missing constraint, or best prompt\. Letaabe either a context action or a task action, and letoobe the resulting reply, trace, or observation, modeled byp​\(o∣x,a\)p\(o\\mid x,a\)\. For each candidate action, an inner inference step updates beliefs overxxunder possible observations\. An outer step then chooses the action that minimizes expected free energy, including risk, epistemic value, and cost\. Under exact inference and deterministic observations, the epistemic term is expected information gain\. The rule is simple\. Acquire more context only when the expected reduction in relevant uncertainty justifies its cost\.

To make uncertainty measurable, we instantiate the idea in*Optimal Question Asking*\(OQA\)\. OQA turns question asking into a controlled Twenty Questions game\(Jedynaket al\.,[2012](https://arxiv.org/html/2608.19202#bib.bib19)\)over a finite attribute table\. A hidden target is sampled uniformly\. The agent asks about one listed attribute per turn\. Answers are obtained by table lookup, either yes/no for binary tables or categorical values forkk\-ary tables\. Each transcript induces a remaining consistent setCtC\_\{t\}, or an equivalence class when several items share the same attribute vector\. With noiseless answers, the posterior is uniform overCtC\_\{t\}, so uncertainty is exact and entropy islog2⁡\|Ct\|\\log\_\{2\}\|C\_\{t\}\|\. We also compute the optimal expected number of questions under the same allowed queries using dynamic programming\. This gives a direct planning gap against an oracle\.

We then test the same accounting view in two token\-budgeted prompting workflows\. In*prompt autocompletion*, the model may spend a few clarification turns before writing a final description\. In*automated prompt optimization*, the model allocates a fixed evaluation budget across prompt variants and uses outcomes to infer which prompt is best\. In both cases, tokens buy evidence about a hidden choice that matters for the final decision\.

This framing is close to reinforcement learning and control\-as\-inference\(Levine,[2018](https://arxiv.org/html/2608.19202#bib.bib77); Millidgeet al\.,[2020](https://arxiv.org/html/2608.19202#bib.bib76)\)\. We do not treat active inference as a rival to RL\. The distinction is operational\. In context\-acquisition settings, the agent can choose the next measurement and thereby shape the evidence stream before acting\. Expected free energy gives a compact language for that choice\.

### 1\.1Main Contributions

- •Context acquisition as active inference\.We cast questions, retrievals, tool calls, prompt trials, and inspections as actions whose purpose is to improve beliefs before a task action\.
- •A bilevel one\-step formulation\.We separate the inner belief update under a hypothetical observation from the outer choice of the next context action, task action, or stop action that minimizes expected free energy under cost\.
- •OQA, a benchmark with exact uncertainty\.We introduce*Optimal Question Asking*\(OQA\), a deterministic attribute\-table benchmark in which a model identifies a hidden target by asking informative questions\.
- •Oracle baselines and stopping rules\.For a fixed table, we compute an optimal questioning strategy using dynamic programming, and state value\-of\-information conditions for when context acquisition is worth its cost\.
- •Two prompting case studies with token budgets\.We apply the same accounting view to clarification before generation and automated prompt optimization, reading token spending as active experiment selection\.

We validate these ideas empirically in OQA on seven frontier models111Models: GPT\-5, GPT\-4\.1, Gemini 2\.5 Pro, Gemini 2\.0 Flash, Claude Sonnet 4\.5, Claude Haiku 4\.5, and Grok 4\.via API, and in both prompting studies\.

In the appendix, we include a discussion of how the bilevel view of one\-step active inference can be used to mathematically model adaptive prompt attacks and possible defenses\. We also discuss the structural similarities and differences between active inference and bilevel reinforcement learning\.

## 2Related Work

Active inference\(Fristonet al\.,[2017](https://arxiv.org/html/2608.19202#bib.bib22); Parr and Friston,[2019](https://arxiv.org/html/2608.19202#bib.bib23)\)extends classical inference by incorporating ideas from control theory\. The core idea is to select actions that maximize information gain through explicit decomposition of preference and epistemic uncertainty over hidden states\. This information\-theoretic perspective connects to a rich literature on optimal querying and exploration\.

Expected information gain is fundamental in Bayesian experimental design\(Lindley,[1956](https://arxiv.org/html/2608.19202#bib.bib26); Chaloner and Verdinelli,[1995](https://arxiv.org/html/2608.19202#bib.bib27); Rainforthet al\.,[2024](https://arxiv.org/html/2608.19202#bib.bib73)\)and drives action selection in active learning and Bayesian optimization through analogous mutual information objectives\(Houlsbyet al\.,[2011](https://arxiv.org/html/2608.19202#bib.bib29); Hennig and Schuler,[2012](https://arxiv.org/html/2608.19202#bib.bib31)\)\. Similarly, information\-directed sampling in bandits balances regret against information acquisition\(Russo and Van Roy,[2014](https://arxiv.org/html/2608.19202#bib.bib60)\)\. A closely related line of work establishes stopping rules for interactions as a function of query cost\(Haertelet al\.,[2008](https://arxiv.org/html/2608.19202#bib.bib34); Bloodgood and Vijay\-Shanker,[2009](https://arxiv.org/html/2608.19202#bib.bib36)\)\.

#### LLM information seeking and clarification\.

Recent work has begun to treat LLMs as active information seekers rather than passive respondents\. UoT uses uncertainty\-aware simulation and information\-gain\-motivated rewards to select follow\-up questions\(Huet al\.,[2024](https://arxiv.org/html/2608.19202#bib.bib80)\)\. Active preference inference uses probabilistic models induced by LLM prompts to ask informative preference questions\(Piriyakulkijet al\.,[2023](https://arxiv.org/html/2608.19202#bib.bib81)\)\. CLAMBER evaluates whether models detect and clarify ambiguous information needs\(Zhanget al\.,[2024](https://arxiv.org/html/2608.19202#bib.bib82)\), while Ask\-when\-Needed studies tool\-use failures under unclear instructions\(Wanget al\.,[2024](https://arxiv.org/html/2608.19202#bib.bib83)\)\. Active Task Disambiguation and BED\-LLM both frame clarification as Bayesian experimental design for LLM agents\(Kobalczyket al\.,[2025](https://arxiv.org/html/2608.19202#bib.bib84); Choudhuryet al\.,[2025](https://arxiv.org/html/2608.19202#bib.bib85)\)\. Complementary work on termination, such as CaRT, studies when an agent has gathered enough information to stop and act\(Liuet al\.,[2025](https://arxiv.org/html/2608.19202#bib.bib86)\)\. Our work connects these directions to the active\-inference expected\-free\-energy decomposition and adds exact oracle diagnostics through OQA\.

Our setting, optimal question asking \(OQA\), instantiates these ideas in a Twenty Questions framework\. Here, successive queries partition a hypothesis set until one target remains\(Jedynaket al\.,[2012](https://arxiv.org/html/2608.19202#bib.bib19)\)\. Generalized binary search provides optimal splitting strategies under deterministic answers\(Nowak,[2011](https://arxiv.org/html/2608.19202#bib.bib61)\), with extensions handling noisy responses and group identification\(Nowak,[2009](https://arxiv.org/html/2608.19202#bib.bib37); Bellalaet al\.,[2010](https://arxiv.org/html/2608.19202#bib.bib38)\)\. Algorithmically, our approach mirrors the bilevel optimization structure of meta\-learning: an inner loop updates beliefs given an answer, while an outer loop selects which question maximizes expected utility\(Colsonet al\.,[2007](https://arxiv.org/html/2608.19202#bib.bib41); Franceschiet al\.,[2018](https://arxiv.org/html/2608.19202#bib.bib44)\)\. This parallels intrinsic motivation in RL, where information gain drives exploration\(Houthooftet al\.,[2016](https://arxiv.org/html/2608.19202#bib.bib45); Pathaket al\.,[2017](https://arxiv.org/html/2608.19202#bib.bib46)\), and prompt optimization methods that search over discrete or continuous prompt spaces\(Shinet al\.,[2020](https://arxiv.org/html/2608.19202#bib.bib47); Zhouet al\.,[2023](https://arxiv.org/html/2608.19202#bib.bib50)\)\. Active inference agents have been deployed in similar settings, from OpenAI Gym environments\(Cullenet al\.,[2018](https://arxiv.org/html/2608.19202#bib.bib15)\)to cognitive models of visual search\(Cullenet al\.,[2020](https://arxiv.org/html/2608.19202#bib.bib17)\)\.

#### Active inference and reinforcement learning\.

A sharp separation between active inference and RL would be misleading\. Control\-as\-inference shows how RL objectives can be represented as probabilistic inference problems\(Levine,[2018](https://arxiv.org/html/2608.19202#bib.bib77)\), and Millidge and coauthors show that active inference and control\-as\-inference differ mainly in how rewards, goals, or preferences are encoded in the graphical model\(Millidgeet al\.,[2020](https://arxiv.org/html/2608.19202#bib.bib76); Millidge,[2021](https://arxiv.org/html/2608.19202#bib.bib75)\)\. Millidge’s retrospective makes the same point in plain language, while also emphasizing that the expected\-free\-energy objective foregrounds information gain and exploration\(Millidge,[2024](https://arxiv.org/html/2608.19202#bib.bib74); Millidgeet al\.,[2021](https://arxiv.org/html/2608.19202#bib.bib79)\)\. Our contribution is therefore not the claim that active inference is categorically different from RL\. It is the claim that the active\-inference decomposition gives a compact design language for LLM systems that can choose what evidence to buy before acting\.

Table 1:Operational distinction used in this paper\. The contrast is not categorical: RL can include information bonuses, and active inference can use RL solvers\.

## 3One\-Step Active Inference as Bilevel Optimization

In single step active inference we separate belief update from action selection\. Letx∈𝒳x\\in\\mathcal\{X\}be a latent state, leta∈𝒜a\\in\\mathcal\{A\}be an action, and leto∈𝒪o\\in\\mathcal\{O\}be the next observation\. Given a likelihoodpθ​\(o∣x,a\)p\_\{\\theta\}\(o\\mid x,a\)and a current beliefqt​\(x\)q\_\{t\}\(x\), define the predictive distribution

qt​\(o∣a\)\\displaystyle q\_\{t\}\(o\\mid a\)=∫pθ​\(o∣x,a\)​qt​\(x\)​𝑑x,\\displaystyle=\\int p\_\{\\theta\}\(o\\mid x,a\)\\,q\_\{t\}\(x\)\\,dx,\(1\)qt​\(x∣o,a\)\\displaystyle q\_\{t\}\(x\\mid o,a\)=pθ​\(o∣x,a\)​qt​\(x\)qt​\(o∣a\),\\displaystyle=\\frac\{p\_\{\\theta\}\(o\\mid x,a\)\\,q\_\{t\}\(x\)\}\{q\_\{t\}\(o\\mid a\)\},\(2\)assumingqt​\(o∣a\)\>0q\_\{t\}\(o\\mid a\)\>0for the relevantoo\. In discrete settings, we can replace integrals with sums\. Unless stated otherwise,log\\logdenotes the natural logarithm, so KL and mutual information are in nats; OQA reports entropy in bits\.

Fix\(a,o\)\(a,o\)and letq​\(x\)∈𝒬q\(x\)\\in\\mathcal\{Q\}be a candidate posterior\. We define the variational free energy

Ft​\(q;a,o\)\\displaystyle F\_\{t\}\(q;a,o\)=𝔼q​\(x\)​\[log⁡q​\(x\)−log⁡pθ​\(o∣x,a\)−log⁡qt​\(x\)\]\\displaystyle=\\mathbb\{E\}\_\{q\(x\)\}\\\!\\Big\[\\log q\(x\)\-\\log p\_\{\\theta\}\(o\\mid x,a\)\-\\log q\_\{t\}\(x\)\\Big\]\(3\)=−logqt\(o∣a\)\+KL\(q\(x\)∥qt\(x∣o,a\)\)\.\\displaystyle=\-\\log q\_\{t\}\(o\\mid a\)\+\\mathrm\{KL\}\\\!\\big\(q\(x\)\\,\\\|\\,q\_\{t\}\(x\\mid o,a\)\\big\)\.\(4\)The inner update is

qt\+1⋆​\(⋅;a,o\)∈arg⁡minq∈𝒬⁡Ft​\(q;a,o\)\.q\_\{t\+1\}^\{\\star\}\(\\cdot;a,o\)\\in\\arg\\min\_\{q\\in\\mathcal\{Q\}\}F\_\{t\}\(q;a,o\)\.\(5\)If𝒬\\mathcal\{Q\}containsqt\(⋅∣o,a\)q\_\{t\}\(\\cdot\\mid o,a\), thenqt\+1⋆​\(x;a,o\)=qt​\(x∣o,a\)q\_\{t\+1\}^\{\\star\}\(x;a,o\)=q\_\{t\}\(x\\mid o,a\)\. In the proof of concept experiments,𝒬\\mathcal\{Q\}contains the exact posterior, so the inner update is closed form\.

Preferences over observations are represented by a distributionp⋆​\(o\)p^\{\\star\}\(o\)\. A standard one step expected free energy includes a term that penalizes ambiguity in the observation model throughH​\(o∣x,a\)H\(o\\mid x,a\)\. In the deterministic answer settings used in OQA, this ambiguity term is zero, and the action score can be written as

Gt​\(a\)\\displaystyle G\_\{t\}\(a\)=𝔼o∼qt\(⋅∣a\)​\[−log⁡p⋆​\(o\)\]⏟expected risk\\displaystyle=\\underbrace\{\\mathbb\{E\}\_\{o\\sim q\_\{t\}\(\\cdot\\mid a\)\}\\\!\\big\[\-\\log p^\{\\star\}\(o\)\\big\]\}\_\{\\text\{expected risk\}\}\(6\)−𝔼o∼qt\(⋅∣a\)​\[KL​\(qt\+1⋆​\(⋅;a,o\)∥qt​\(⋅\)\)\]⏟expected KL change in belief\.\\displaystyle\\quad\-\\underbrace\{\\mathbb\{E\}\_\{o\\sim q\_\{t\}\(\\cdot\\mid a\)\}\\\!\\Big\[\\mathrm\{KL\}\\\!\\big\(q\_\{t\+1\}^\{\\star\}\(\\cdot;a,o\)\\,\\\|\\,q\_\{t\}\(\\cdot\)\\big\)\\Big\]\}\_\{\\text\{expected KL change in belief\}\}\.With an exact inner update, the second term is an information gain term, as made explicit below\.

###### Proposition 3\.1\(Mutual\-information form and deterministic special case\)\.

Assume the inner solution is exact,qt\+1⋆​\(x;a,o\)=qt​\(x∣o,a\)q\_\{t\+1\}^\{\\star\}\(x;a,o\)=q\_\{t\}\(x\\mid o,a\), with predictiveqt​\(o∣a\)q\_\{t\}\(o\\mid a\)from \([1](https://arxiv.org/html/2608.19202#S3.E1)\)\. Then

𝔼o∼qt\(⋅∣a\)​\[KL​\(qt\+1⋆​\(⋅;a,o\)∥qt​\(⋅\)\)\]=Iqt​\(x;o∣a\),\\mathbb\{E\}\_\{o\\sim q\_\{t\}\(\\cdot\\mid a\)\}\\\!\\Big\[\\mathrm\{KL\}\\\!\\big\(q\_\{t\+1\}^\{\\star\}\(\\cdot;a,o\)\\,\\\|\\,q\_\{t\}\(\\cdot\)\\big\)\\Big\]=I\_\{q\_\{t\}\}\(x;o\\mid a\),\(7\)the mutual information under the jointqt​\(x\)​pθ​\(o∣x,a\)q\_\{t\}\(x\)\\,p\_\{\\theta\}\(o\\mid x,a\)\. Ifp⋆p^\{\\star\}is constant, the risk term in \([6](https://arxiv.org/html/2608.19202#S3.E6)\) is independent ofaa, so

a⋆∈arg⁡mina⁡Gt​\(a\)⟺a⋆∈arg⁡maxa⁡Iqt​\(x;o∣a\)\.a^\{\\star\}\\in\\arg\\min\_\{a\}G\_\{t\}\(a\)\\quad\\Longleftrightarrow\\quad a^\{\\star\}\\in\\arg\\max\_\{a\}I\_\{q\_\{t\}\}\(x;o\\mid a\)\.\(8\)Moreover,

Iqt​\(x;o∣a\)=Hqt​\(o∣a\)−𝔼x∼qt​H​\(o∣x,a\)\.I\_\{q\_\{t\}\}\(x;o\\mid a\)=H\_\{q\_\{t\}\}\(o\\mid a\)\-\\mathbb\{E\}\_\{x\\sim q\_\{t\}\}H\(o\\mid x,a\)\.\(9\)IfH​\(o∣x,a\)=0H\(o\\mid x,a\)=0forqtq\_\{t\}\-a\.e\.xx, for example in discrete deterministic observation models, thenIqt​\(x;o∣a\)=Hqt​\(o∣a\)I\_\{q\_\{t\}\}\(x;o\\mid a\)=H\_\{q\_\{t\}\}\(o\\mid a\)\.

###### Proof\.

By definition under the jointqt​\(x\)​pθ​\(o∣x,a\)q\_\{t\}\(x\)\\,p\_\{\\theta\}\(o\\mid x,a\),

Iqt​\(x;o∣a\)=𝔼o∼qt\(⋅∣a\)​\[KL​\(qt​\(x∣o,a\)∥qt​\(x\)\)\]\.I\_\{q\_\{t\}\}\(x;o\\mid a\)=\\mathbb\{E\}\_\{o\\sim q\_\{t\}\(\\cdot\\mid a\)\}\\\!\\big\[\\mathrm\{KL\}\(q\_\{t\}\(x\\mid o,a\)\\\|q\_\{t\}\(x\)\)\\big\]\.Substitutingqt\+1⋆=qt\(⋅∣o,a\)q\_\{t\+1\}^\{\\star\}=q\_\{t\}\(\\cdot\\mid o,a\)gives \([7](https://arxiv.org/html/2608.19202#S3.E7)\)\. Ifp⋆p^\{\\star\}is constant,𝔼o​\[−log⁡p⋆​\(o\)\]\\mathbb\{E\}\_\{o\}\[\-\\log p^\{\\star\}\(o\)\]does not depend onaa, which yields \([8](https://arxiv.org/html/2608.19202#S3.E8)\)\. The identity \([9](https://arxiv.org/html/2608.19202#S3.E9)\) is the standard entropy decomposition of mutual information\. ∎

The dependence of \([6](https://arxiv.org/html/2608.19202#S3.E6)\) on the optimizer in \([5](https://arxiv.org/html/2608.19202#S3.E5)\) yields the bilevel program:

mina∈𝒜Gt​\(a\)s\.t\.qt\+1⋆​\(⋅;a,o\)∈arg⁡minq∈𝒬⁡Ft​\(q;a,o\),∀o∈𝒪​with​qt​\(o∣a\)\>0\.\\boxed\{\\begin\{aligned\} \\min\_\{a\\in\\mathcal\{A\}\}\\quad&G\_\{t\}\(a\)\\\\ \\text\{s\.t\.\}\\quad&q\_\{t\+1\}^\{\\star\}\(\\cdot;a,o\)\\in\\arg\\min\_\{q\\in\\mathcal\{Q\}\}\\,F\_\{t\}\(q;a,o\),\\\\ &\\forall o\\in\\mathcal\{O\}\\ \\text\{with\}\\ q\_\{t\}\(o\\mid a\)\>0\.\\end\{aligned\}\}\(10\)The outer expectation inGt​\(a\)G\_\{t\}\(a\)is taken overo∼qt\(⋅∣a\)o\\sim q\_\{t\}\(\\cdot\\mid a\)\.

###### Proposition 3\.2\(Differentiability of the bilevel objective\)\.

Let𝒬=\{qϕ:ϕ∈ℝm\}\\mathcal\{Q\}=\\\{q\_\{\\phi\}:\\phi\\in\\mathbb\{R\}^\{m\}\\\}and writeFt​\(ϕ;a,o\):=Ft​\(qϕ;a,o\)F\_\{t\}\(\\phi;a,o\):=F\_\{t\}\(q\_\{\\phi\};a,o\)\. Define

ϕ⋆​\(a,o\)\\displaystyle\\phi^\{\\star\}\(a,o\)∈arg⁡minϕ⁡Ft​\(ϕ;a,o\),\\displaystyle\\in\\arg\\min\_\{\\phi\}F\_\{t\}\(\\phi;a,o\),\(11\)Gt​\(a\)\\displaystyle G\_\{t\}\(a\)=𝔼o∼qt\(⋅∣a\)​\[ℒ​\(a,o,ϕ⋆​\(a,o\)\)\],\\displaystyle=\\mathbb\{E\}\_\{o\\sim q\_\{t\}\(\\cdot\\mid a\)\}\\big\[\\mathcal\{L\}\(a,o,\\phi^\{\\star\}\(a,o\)\)\\big\],for a differentiable outer integrandℒ\\mathcal\{L\}\. Suppose that for relevant\(a,o\)\(a,o\)the minimizerϕ⋆​\(a,o\)\\phi^\{\\star\}\(a,o\)is isolated, thatFt​\(ϕ;a,o\)F\_\{t\}\(\\phi;a,o\)is twice continuously differentiable in\(a,ϕ\)\(a,\\phi\), and that∇ϕ​ϕ2Ft​\(ϕ⋆;a,o\)≻0\\nabla^\{2\}\_\{\\phi\\phi\}F\_\{t\}\(\\phi^\{\\star\};a,o\)\\succ 0\. Thenϕ⋆​\(a,o\)\\phi^\{\\star\}\(a,o\)is locally differentiable inaa\. If, in addition,qt​\(o∣a\)q\_\{t\}\(o\\mid a\)andℒ\\mathcal\{L\}satisfy standard conditions for differentiating under the expectation, thenGt​\(a\)G\_\{t\}\(a\)is differentiable\. Gradients can be computed by implicit differentiation or by unrolling an inner solver\. For discrete𝒜\\mathcal\{A\}, \([6](https://arxiv.org/html/2608.19202#S3.E6)\) can be evaluated by enumeration, or by a differentiable relaxation\.

###### Proof sketch\.

At an isolated minimizer,∇ϕFt​\(ϕ⋆;a,o\)=0\\nabla\_\{\\phi\}F\_\{t\}\(\\phi^\{\\star\};a,o\)=0\. If∇ϕ​ϕ2Ft​\(ϕ⋆;a,o\)≻0\\nabla^\{2\}\_\{\\phi\\phi\}F\_\{t\}\(\\phi^\{\\star\};a,o\)\\succ 0, the Jacobian with respect toϕ\\phiis invertible, so the implicit function theorem yields local differentiability ofϕ⋆​\(a,o\)\\phi^\{\\star\}\(a,o\)inaaand the standard implicit gradient expression\. ∎

###### Proposition 3\.3\(Information\-per\-cost stopping rule\)\.

Suppose the inner update is exact, preferences are constant over the possible observations of each information\-gathering action, and taking no further measurement has score0\. Let actionaahave expected costc​\(a\)\>0c\(a\)\>0, and let the one\-step objective be expected posterior entropy plus a cost penaltyλ​c​\(a\)\\lambda c\(a\), withλ\>0\\lambda\>0\. Then an information\-gathering action is worthwhile exactly when

Iqt​\(x;o∣a\)\>λ​c​\(a\)\.I\_\{q\_\{t\}\}\(x;o\\mid a\)\>\\lambda c\(a\)\.\(12\)Among worthwhile actions, the optimal one maximizesIqt​\(x;o∣a\)−λ​c​\(a\)I\_\{q\_\{t\}\}\(x;o\\mid a\)\-\\lambda c\(a\)\. Equivalently, if a fixed cost budget is spent greedily in small units, the myopic selector ranks actions by information gained per unit cost\.

###### Proof\.

For a fixed current belief,Hqt​\(x\)H\_\{q\_\{t\}\}\(x\)is independent of the next action\. Exact Bayes gives

𝔼o∼qt\(⋅∣a\)​Hqt​\(x∣o,a\)=Hqt​\(x\)−Iqt​\(x;o∣a\)\.\\mathbb\{E\}\_\{o\\sim q\_\{t\}\(\\cdot\\mid a\)\}H\_\{q\_\{t\}\}\(x\\mid o,a\)=H\_\{q\_\{t\}\}\(x\)\-I\_\{q\_\{t\}\}\(x;o\\mid a\)\.Adding the cost penalty yields the one\-step scoreHqt​\(x\)−Iqt​\(x;o∣a\)\+λ​c​\(a\)H\_\{q\_\{t\}\}\(x\)\-I\_\{q\_\{t\}\}\(x;o\\mid a\)\+\\lambda c\(a\)\. Subtracting the no\-measurement scoreHqt​\(x\)H\_\{q\_\{t\}\}\(x\)givesλ​c​\(a\)−Iqt​\(x;o∣a\)\\lambda c\(a\)\-I\_\{q\_\{t\}\}\(x;o\\mid a\)\. Thus asking is beneficial precisely when \([12](https://arxiv.org/html/2608.19202#S3.E12)\) holds, and the maximizing rule follows by dropping the action\-independent entropy term\. ∎

###### Theorem 3\.4\(Bayes\-risk value of context\)\.

Let𝒟\\mathcal\{D\}be a set of terminal decisions and letℓ​\(d,x\)\\ell\(d,x\)be a finite loss\. For a beliefqqoverxx, define the Bayes risk

R​\(q\)=mind∈𝒟⁡𝔼x∼q​ℓ​\(d,x\)\.R\(q\)=\\min\_\{d\\in\\mathcal\{D\}\}\\mathbb\{E\}\_\{x\\sim q\}\\,\\ell\(d,x\)\.\(13\)Consider a context\-acquisition actionaawith costc​\(a\)\>0c\(a\)\>0, predictive distributionqt​\(o∣a\)q\_\{t\}\(o\\mid a\), and exact posteriorqt\(⋅∣o,a\)q\_\{t\}\(\\cdot\\mid o,a\)after observingoo\. Suppose the agent may either act immediately, incurring riskR​\(qt\)R\(q\_\{t\}\), or take one context actionaaand then act optimally under the resulting posterior, incurring expected score

𝔼o∼qt\(⋅∣a\)R\(qt\(⋅∣o,a\)\)\+λc\(a\)\.\\mathbb\{E\}\_\{o\\sim q\_\{t\}\(\\cdot\\mid a\)\}R\(q\_\{t\}\(\\cdot\\mid o,a\)\)\+\\lambda c\(a\)\.\(14\)Thenaais strictly preferred to acting now exactly when

R\(qt\)−𝔼o∼qt\(⋅∣a\)R\(qt\(⋅∣o,a\)\)\>λc\(a\)\.R\(q\_\{t\}\)\-\\mathbb\{E\}\_\{o\\sim q\_\{t\}\(\\cdot\\mid a\)\}R\(q\_\{t\}\(\\cdot\\mid o,a\)\)\>\\lambda c\(a\)\.\(15\)If the terminal loss is logarithmic and the terminal decision is a predictive distribution, thenR​\(q\)=H​\(q\)R\(q\)=H\(q\)and the left side of \([15](https://arxiv.org/html/2608.19202#S3.E15)\) isIqt​\(x;o∣a\)I\_\{q\_\{t\}\}\(x;o\\mid a\)\.

###### Proof\.

Acting immediately gives the optimal terminal riskR​\(qt\)R\(q\_\{t\}\)by definition\. Takingaafirst gives an observation\-dependent posterior and then the optimal terminal risk for that posterior, plus the cost penalty\. Comparing the two scores yields \([15](https://arxiv.org/html/2608.19202#S3.E15)\)\. For logarithmic loss, the Bayes\-optimal predictive distribution is the belief itself and the Bayes risk is entropy\. The expected entropy reduction identity gives

H\(qt\)−𝔼o∼qt\(⋅∣a\)H\(qt\(⋅∣o,a\)\)=Iqt\(x;o∣a\),H\(q\_\{t\}\)\-\\mathbb\{E\}\_\{o\\sim q\_\{t\}\(\\cdot\\mid a\)\}H\(q\_\{t\}\(\\cdot\\mid o,a\)\)=I\_\{q\_\{t\}\}\(x;o\\mid a\),which proves the final claim\. ∎

## 4Active Inference as Context Acquisition

The preceding objective can be read as an inference\-time control layer for AI agents\. The agent maintains a belief over latent task state, then chooses among context actions, task actions, and stopping\. A context action is any move that primarily changes the information available to the agent: asking the user, retrieving a passage, calling a tool to fill a missing field, evaluating a prompt variant, or inspecting part of an input\. A task action is the move that commits to the requested output\.

This view separates three roles that are often mixed in prompting practice\. The*belief state*stores what the agent currently thinks is true about the task\. The*measurement model*says what each context action could reveal\. The*preference or loss model*says which terminal outcomes matter\. Expected free energy then scores a candidate context action by how much it is expected to reduce decision\-relevant uncertainty, not merely by whether it seems like a reasonable question\.

Algorithm 1: AIF\-Context at inference timeAt turntt, maintain a beliefqt​\(x\)q\_\{t\}\(x\)over latent task state\.1\.Propose a small action set𝒜tctx\\mathcal\{A\}\_\{t\}^\{\\mathrm\{ctx\}\}of context actions and a set𝒜ttask\\mathcal\{A\}\_\{t\}^\{\\mathrm\{task\}\}of terminal task actions\.2\.For eacha∈𝒜tctxa\\in\\mathcal\{A\}\_\{t\}^\{\\mathrm\{ctx\}\}, predict possible observations withqt​\(o∣a\)q\_\{t\}\(o\\mid a\)and compute the posteriorqt​\(x∣o,a\)q\_\{t\}\(x\\mid o,a\)that would follow each observation\.3\.Scoreaaby expected free energy, or by the Bayes\-risk value of context in[Theorem˜3\.4](https://arxiv.org/html/2608.19202#S3.Thmtheorem4)when a terminal loss is available\.4\.If no context action beats acting now after cost, choose the best task action\. Otherwise execute the best context action, observeoto\_\{t\}, updateqt\+1q\_\{t\+1\}, and repeat\.

OQA instantiates this loop with a finite candidate set, deterministic measurements, and exact posteriors\. Prompt autocompletion instantiates it with a latent style variable and fixed clarification templates\. Prompt optimization instantiates it with a latent best\-prompt identity and automatically scored trials\. These are deliberately restricted cases, but the abstraction is broader: an AI agent can treat every token, query, tool call, or inspection as an experiment that competes against acting now\.

The framework also clarifies what OQA does not claim\. In deterministic OQA with flat observation preferences, one\-step expected free energy reduces to greedy expected information gain\. Greedy information gain is a useful local rule, but it is not the same as the globally optimal policy over a full dialogue\. The dynamic programming oracle therefore plays a conceptual role beyond benchmarking: it measures the cost of myopic context acquisition\.

## 5Binary OQA Experiments: 25 and 100 Candidates

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/25_places_entropy_plot.png)

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/25_cars_entropy_plot.png)

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/25_animals_entropy_plot.png)

Figure 1:Binary OQA withN=25N=25\. Curves show mean entropyHt=log2⁡\|Ct\|H\_\{t\}=\\log\_\{2\}\|C\_\{t\}\|across uniformly sampled targets, with±1\\pm 1standard deviation, along with the DP oracle\.![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/100_places_entropy_plot.png)

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/100_cars_entropy_plot.png)

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/100_animals_entropy_plot.png)

Figure 2:Binary OQA withN=100N=100\. Curves show mean entropyHt=log2⁡\|Ct\|H\_\{t\}=\\log\_\{2\}\|C\_\{t\}\|across uniformly sampled targets, with±1\\pm 1standard deviation, along with the DP oracle\. In Animals, duplicate attribute vectors can force stopping with a small residual entropy\.Binary OQA starts with a set𝒳\\mathcal\{X\}ofNNitems\. Each item has a fixed yes or no value for each of the same attribute names, which can be viewed as its attribute vector\. For example, in an animals table the item “cat” might have values like “mammal = yes,” “has\_fur = yes,” and “can\_swim = no\.” One itemx⋆x^\{\\star\}is chosen uniformly at random as the hidden target, and the candidate set starts atC0=𝒳C\_\{0\}=\\mathcal\{X\}\. Each turn asks for one attribute value and removes all items that disagree with the replies so far, leaving the updated candidate setCtC\_\{t\}\. With a uniform prior and noiseless answers, the belief is uniform onCtC\_\{t\}\. The uncertainty isHt=log2⁡\|Ct\|H\_\{t\}=\\log\_\{2\}\|C\_\{t\}\|and per question progress isΔ​Ht=Ht−Ht\+1\\Delta H\_\{t\}=H\_\{t\}\-H\_\{t\+1\}\. A run ends when\|Ct\|=1\|C\_\{t\}\|=1, or earlier when no attribute can splitCtC\_\{t\}\. The latter happens when the remaining items share the same full attribute vector, so some runs can end withHt\>0H\_\{t\}\>0\.

LetTmodel​\(x⋆\)T\_\{\\text\{model\}\}\(x^\{\\star\}\)be the model’s count andTDP​\(x⋆\)T\_\{\\text\{DP\}\}\(x^\{\\star\}\)the DP oracle’s count under the same attribute menu and stopping rule\. We define the metric “planning gap" as the average number of extra questions the model uses compared to the oracle,𝔼x⋆∼Unif​\(𝒳\)​\[Tmodel​\(x⋆\)−TDP​\(x⋆\)\]\.\\mathbb\{E\}\_\{x^\{\\star\}\\sim\\mathrm\{Unif\}\(\\mathcal\{X\}\)\}\\\!\\left\[T\_\{\\text\{model\}\}\(x^\{\\star\}\)\-T\_\{\\text\{DP\}\}\(x^\{\\star\}\)\\right\]\.A simple baseline is a greedy strategy that picks the attribute with the largest expected reduction in uncertainty\. For a candidate setCCand a yes or no attributejj, askingjjsplitsCCintoCyesC^\{\\text\{yes\}\}andCnoC^\{\\text\{no\}\}\. Near\-balanced splits tend to be most informative\. In this deterministic setting, the expected entropy reduction equals mutual information up to the log base, but it is optimal only for the next step and can be suboptimal over multiple steps\.

Our DP oracle is optimal in the sense that it minimizes the expected number of questions until stopping\. LetCost​\(C\)\\mathrm\{Cost\}\(C\)be the optimal expected number of additional questions when the remaining candidate set isCC, assuming the hidden target is uniform onCC\. If an attributejjsplitsCCintoCyesC^\{\\text\{yes\}\}andCnoC^\{\\text\{no\}\}, then askingjjcosts one question plus the expected remaining cost weighted by branch sizes, givingCost​\(C\)=\\mathrm\{Cost\}\(C\)=

minj:Cyes,Cno≠∅⁡\(1\+\|Cyes\|\|C\|​Cost​\(Cyes\)\+\|Cno\|\|C\|​Cost​\(Cno\)\),\\min\_\{j:\\ C^\{\\text\{yes\}\},C^\{\\text\{no\}\}\\neq\\emptyset\}\\left\(1\+\\frac\{\|C^\{\\text\{yes\}\}\|\}\{\|C\|\}\\mathrm\{Cost\}\(C^\{\\text\{yes\}\}\)\+\\frac\{\|C^\{\\text\{no\}\}\|\}\{\|C\|\}\\mathrm\{Cost\}\(C^\{\\text\{no\}\}\)\\right\),\(16\)withCost​\(C\)=0\\mathrm\{Cost\}\(C\)=0when\|C\|≤1\|C\|\\leq 1or when no attribute can splitCC\.

###### Theorem 5\.1\(Optimality of the deterministic OQA oracle\)\.

Consider any finite deterministic OQA game with candidate setCC, a uniform target withinCC, a finite menu of allowed queries, and unit query cost\. Each queryaapartitionsCCinto nonempty cells\{Co​\(a\):o∈𝒪a\}\\\{C\_\{o\}\(a\):o\\in\\mathcal\{O\}\_\{a\}\\\}, and terminal sets are those with one candidate or no query that can split them\. Let

V​\(C\)=\{0,C​terminal,mina⁡\(1\+∑o∈𝒪a\|Co​\(a\)\|\|C\|​V​\(Co​\(a\)\)\),otherwise,V\(C\)=\\begin\{cases\}0,&C\\text\{ terminal\},\\\\\[5\.69054pt\] \\displaystyle\\min\_\{a\}\\left\(1\+\\sum\_\{o\\in\\mathcal\{O\}\_\{a\}\}\\frac\{\|C\_\{o\}\(a\)\|\}\{\|C\|\}V\(C\_\{o\}\(a\)\)\\right\),&\\text\{otherwise\},\\end\{cases\}\(17\)where the minimum ranges over queries that splitCC\. ThenV​\(C\)V\(C\)is the minimum expected number of additional queries over all allowed adaptive decision trees\. Any policy that attains the minimum in \([17](https://arxiv.org/html/2608.19202#S5.E17)\) at every reachable set is optimal\.

###### Proof\.

The proof is by induction on\|C\|\|C\|\. Terminal sets have value zero by definition\. For nonterminalCC, any valid decision tree must choose some first queryaa, pay one unit of cost, and then continue independently inside the cellCo​\(a\)C\_\{o\}\(a\)selected by the truthful answer\. Since the target is uniform onCC, that cell occurs with probability\|Co​\(a\)\|/\|C\|\|C\_\{o\}\(a\)\|/\|C\|\. By the induction hypothesis, the best possible continuation cost in each branch isV​\(Co​\(a\)\)V\(C\_\{o\}\(a\)\)\. Thus every decision tree has expected cost at least the right side of \([17](https://arxiv.org/html/2608.19202#S5.E17)\)\. Choosing a minimizing query and then using optimal subtrees for all child cells attains this bound, so the recurrence is both necessary and sufficient\. ∎

We computeCost​\(C\)\\mathrm\{Cost\}\(C\)with caching, since the same candidate set can arise from different question sequences\. To plot an oracle trace for a fixed targetx⋆x^\{\\star\}, start fromC0=𝒳C\_\{0\}=\\mathcal\{X\}\. At turntt, choose an attribute that minimizes \([16](https://arxiv.org/html/2608.19202#S5.E16)\), filter to obtainCt\+1C\_\{t\+1\}, and recordHt=log2⁡\|Ct\|H\_\{t\}=\\log\_\{2\}\|C\_\{t\}\|\. We run this on Places, Cars, and Animals withN∈\{25,100\}N\\in\\\{25,100\\\}, using one API call per question withtemperature=0, fresh sessions per target, and no external tools\. Figures[1](https://arxiv.org/html/2608.19202#S5.F1)and[2](https://arxiv.org/html/2608.19202#S5.F2)show mean entropy trajectories over uniformly sampled targets, with±1\\pm 1standard deviation, alongside the DP oracle\.

Summary and takeaways\.We evaluate frontier LLMs on 25\- and 100\-tier binary OQA datasets, tracking posterior entropy exactly and comparing each model to a dynamic programming \(DP\) oracle under the same attribute menu and stopping rule\. However, even in a clean setting where uncertainty can be measured exactly, models leave efficiency on the table\. They do make steady progress, but they still ask avoidable questions compared to an optimal strategy\.

## 6Multiway Categorical OQA Experiments: 100, 200, and 300 Candidates

Similar to binary OQA, multiway categorical OQA starts with a set𝒳\\mathcal\{X\}ofNNitems\. Each item has a fixed categorical value for each of the same attribute names, which can be viewed as its attribute vector\. For example, an item might have values likecolor = red,shape = hexagon, andmaterial = steel\. One itemx⋆x^\{\\star\}is chosen uniformly at random as the hidden target, and the candidate set starts atC0=𝒳C\_\{0\}=\\mathcal\{X\}\. Each turn asks for the value of one attribute and removes all items that disagree with the replies so far, leaving the updated candidate setCtC\_\{t\}\. With a uniform prior and deterministic answers, the belief is uniform onCtC\_\{t\}\. As before, the uncertainty isHt=log2⁡\|Ct\|H\_\{t\}=\\log\_\{2\}\|C\_\{t\}\|and per question progress isΔ​Ht=Ht−Ht\+1\\Delta H\_\{t\}=H\_\{t\}\-H\_\{t\+1\}\. A run ends when\|Ct\|=1\|C\_\{t\}\|=1, or earlier when no attribute can splitCtC\_\{t\}\.

Formally, let𝒜\\mathcal\{A\}be the finite attribute set, and for eacha∈𝒜a\\in\\mathcal\{A\}leta:𝒳→𝒱aa:\\mathcal\{X\}\\to\\mathcal\{V\}\_\{a\}map items to a finite value set\. At turnttthe agent choosesat∈𝒜a\_\{t\}\\in\\mathcal\{A\}, observes the truthful replyot=at​\(x⋆\)o\_\{t\}=a\_\{t\}\(x^\{\\star\}\), and filters by consistency,Ct\+1=\{x∈Ct:at​\(x\)=ot\}C\_\{t\+1\}=\\\{x\\in C\_\{t\}:\\ a\_\{t\}\(x\)=o\_\{t\}\\\}\. We call a tierkk\-ary, wherek=maxa∈𝒜⁡\|𝒱a\|k=\\max\_\{a\\in\\mathcal\{A\}\}\|\\mathcal\{V\}\_\{a\}\|\. In our released tiers,k=5k=5\. We keep the early stopping rule above for completeness, although in the released tiers the attribute vectors are unique, so runs end with\|Ct\|=1\|C\_\{t\}\|=1\. As in the binary setting, we summarize planning by questions to stop\. LetTmodel​\(x⋆\)T\_\{\\text\{model\}\}\(x^\{\\star\}\)be the model’s count andTDP​\(x⋆\)T\_\{\\text\{DP\}\}\(x^\{\\star\}\)the DP oracle’s count under the same attribute menu and stopping rule\. The planning gap is𝔼x⋆∼Unif​\(𝒳\)​\[Tmodel​\(x⋆\)−TDP​\(x⋆\)\]\\mathbb\{E\}\_\{x^\{\\star\}\\sim\\mathrm\{Unif\}\(\\mathcal\{X\}\)\}\\\!\\left\[T\_\{\\text\{model\}\}\(x^\{\\star\}\)\-T\_\{\\text\{DP\}\}\(x^\{\\star\}\)\\right\]\.

A simple baseline is a greedy strategy that picks the attribute with the largest expected reduction in uncertainty\. Fix a candidate setCCand an attributeaa\. For each valuev∈𝒱av\\in\\mathcal\{V\}\_\{a\}, defineCv=\{x∈C:a​\(x\)=v\}C\_\{v\}=\\\{x\\in C:\\ a\(x\)=v\\\}\. Under the uniform belief onCC,Pr⁡\[o=v\]=\|Cv\|/\|C\|\\Pr\[o=v\]=\|C\_\{v\}\|/\|C\|, and the expected entropy reduction from askingaaisEIG​\(a;C\)=log2⁡\|C\|−∑v∈𝒱a:\|Cv\|\>0\|Cv\|\|C\|​log2⁡\|Cv\|\.\\mathrm\{EIG\}\(a;C\)=\\log\_\{2\}\|C\|\-\\sum\_\{v\\in\\mathcal\{V\}\_\{a\}:\\,\|C\_\{v\}\|\>0\}\\frac\{\|C\_\{v\}\|\}\{\|C\|\}\\log\_\{2\}\|C\_\{v\}\|\.

Near\-balanced partitions tend to be most informative\. In this deterministic setting,EIG\\mathrm\{EIG\}matches mutual information up to the log base \(Prop\.[3\.1](https://arxiv.org/html/2608.19202#S3.Thmtheorem1)\), but it is optimal only for the next step and can be suboptimal over multiple steps\.

The DP oracle is optimal under our rules, in the sense that it minimizes the expected number of questions until stopping\. LetCost​\(C\)\\mathrm\{Cost\}\(C\)be the optimal expected number of additional questions when the remaining candidate set isCC, assuming the hidden target is uniform onCC\. For an attributeaa, letBa​\(C\)=\{v∈𝒱a:\|Cv\|\>0\}B\_\{a\}\(C\)=\\\{v\\in\\mathcal\{V\}\_\{a\}:\\ \|C\_\{v\}\|\>0\\\}\. If\|Ba​\(C\)\|=1\|B\_\{a\}\(C\)\|=1, thenaadoes not splitCCand is ignored\. Otherwise,Cost​\(C\)=\\mathrm\{Cost\}\(C\)=

mina∈𝒜:\|Ba​\(C\)\|≥2⁡\(1\+∑v∈𝒱a:\|Cv\|\>0\|Cv\|\|C\|​Cost​\(Cv\)\),\\min\_\{a\\in\\mathcal\{A\}:\\,\|B\_\{a\}\(C\)\|\\geq 2\}\\left\(1\+\\sum\_\{v\\in\\mathcal\{V\}\_\{a\}:\\,\|C\_\{v\}\|\>0\}\\frac\{\|C\_\{v\}\|\}\{\|C\|\}\\,\\mathrm\{Cost\}\(C\_\{v\}\)\\right\),\(18\)withCost​\(C\)=0\\mathrm\{Cost\}\(C\)=0when\|C\|≤1\|C\|\\leq 1or when no attribute can splitCC\. We computeCost​\(C\)\\mathrm\{Cost\}\(C\)with caching using a canonical representation ofCC, such as a sorted tuple of item IDs\. To plot an oracle trace for a fixed targetx⋆x^\{\\star\}, start fromC0=𝒳C\_\{0\}=\\mathcal\{X\}\. At turntt, choose an attribute that minimizes \([18](https://arxiv.org/html/2608.19202#S6.E18)\), applyCt\+1=\{x∈Ct:at​\(x\)=ot\}C\_\{t\+1\}=\\\{x\\in C\_\{t\}:\\ a\_\{t\}\(x\)=o\_\{t\}\\\}using the target’s true value, and recordHt=log2⁡\|Ct\|H\_\{t\}=\\log\_\{2\}\|C\_\{t\}\|until stopping\.

We use three tiers with\|𝒳\|∈\{100,200,300\}\|\\mathcal\{X\}\|\\in\\\{100,200,300\\\}\. All tiers share the same eight attributes, namelycolor,shape,material,size,pattern,origin,use\_case, andenergy\. Each query must request the value of exactly one named attribute, and the evaluator answers by table lookup\.

We evaluate3030targets per tier with tool use disabled, using one API call per question withtemperature=0in a fresh session per target\. Mean entropy trajectories are plotted with±1\\pm 1standard deviation alongside the DP oracle in[Figure˜3](https://arxiv.org/html/2608.19202#S6.F3)\.

#### Summary and takeaways\.

We extend OQA to multiway categorical attributes using deterministic table lookups, with 100, 200, and 300 tiers and a fixed menu of eight attributes\. We again track posterior entropy and measure efficiency by planning gap\. Frontier models consistently shrink the consistent set over turns, and yet they remain less question\-efficient than the dynamic programming \(DP\) oracle\.

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/kary100_entropy_plot.png)

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/kary200_entropy_plot.png)

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/kary300_entropy_plot.png)

Figure 3:Multiway categorical OQA for\|𝒳\|∈\{100,200,300\}\|\\mathcal\{X\}\|\\in\\\{100,200,300\\\}\(top to bottom\)\. Curves show mean posterior entropy over uniformly sampled targets\. The DP oracle uses the same query menu and stopping rule\. Error bars show±1\\pm 1standard deviation when available\.

## 7Prompt Autocompletion as Active Inference

This is our first prompt experiment\. Suppose a user asks for a product description but does not specify a style\. Each task provides a product name and three feature phrases\. We model the desired style as a hidden variableU=\(tone,length,format\)U=\(\\text\{tone\},\\text\{length\},\\text\{format\}\)\. The tone is either formal or friendly, length is either short or medium, and format is either bullet points or a paragraph\. We sample these three style choices independently and uniformly\. The agent may ask up to three clarifying questions before writing one final description\. In this experiment, the questions use fixed templates, and we simulate the answers from the hiddenUU\. This keeps the focus on the agent’s choice of what to ask, rather than how the questions are phrased\. Each question targets exactly one component ofUU, and we never ask about the same component twice\.

We assume that the answers are always truthful, and we add uncertainty only when updating the agent’s belief aboutUU, using a symmetric label noise model, so the posterior does not become overly confident\. We also charge a synthetic token cost for each clarification\. The first costsc1=24c\_\{1\}=24tokens, thenc2=48c\_\{2\}=48, thenc3=72c\_\{3\}=72\. After any clarifications, we call the base model once and request a description using the MAP styleU^\\hat\{U\}\. We further assume that the agent’s belief over styles factorizes across the three attributes, soqt​\(U\)=qt​\(tone\)​qt​\(length\)​qt​\(format\)q\_\{t\}\(U\)=q\_\{t\}\(\\text\{tone\}\)\\,q\_\{t\}\(\\text\{length\}\)\\,q\_\{t\}\(\\text\{format\}\), and we start from a uniform prior\. When the agent asks about one attributevv\(tone, length, or format\), it updates onlyqt​\(v\)q\_\{t\}\(v\)\. We model mistakes in this update with a fixed error rateε=0\.12\\varepsilon=0\.12\. The information gained from that question isΔ​It​\(v\)=KL​\(qt\+1​\(v\)∥qt​\(v\)\)\\Delta I\_\{t\}\(v\)=\\mathrm\{KL\}\(q\_\{t\+1\}\(v\)\\,\\\|\\,q\_\{t\}\(v\)\), measured in bits\.

After the agent produces the final description, a deterministic verifier checks it\. The verifier requires each feature phrase to appear as an exact substring, and it checks format and word count\. A short description has at most 70 words, while a medium description has 70 to 160 words\. Tone is not checked, so the sampled style and the verifier reward do not perfectly match\. We compare five question asking policies\.baselineasks no questions and uses the default style\.ask\_allasks about tone, length, and format\.randomsamplesKKuniformly from\{0,1,2,3\}\\\{0,1,2,3\\\}, then asksKKdistinct attributes in random order\.activechooses the unasked attribute with the largest entropy per expected token cost,H​\(qt​\(v\)\)/c\|𝒞\|\+1H\(q\_\{t\}\(v\)\)/c\_\{\|\\mathcal\{C\}\|\+1\}, and stops when this score falls belowϵ\\epsilon\.active\_weighteduses the same rule, but weights the entropy term bywvw\_\{v\}, withwformat=1\.0w\_\{\\text\{format\}\}=1\.0,wlength=0\.6w\_\{\\text\{length\}\}=0\.6, andwtone=0\.25w\_\{\\text\{tone\}\}=0\.25\.

In[Figure˜4](https://arxiv.org/html/2608.19202#S7.F4), we fixϵ=0\.02\\epsilon=0\.02andKmax=3K\_\{\\max\}=3on 48 tasks to show the cost accuracy trade\-off across policies\. We then tuneactive\_weightedvia grid search overϵ∈\{0,0\.005,0\.01,0\.02,0\.04\}\\epsilon\\in\\\{0,0\.005,0\.01,0\.02,0\.04\\\}andKmax∈\{1,2,3\}K\_\{\\max\}\\in\\\{1,2,3\\\}, maximizingJ​\(ϵ,Kmax\)=𝔼​\[ok\]−0\.02​𝔼​\[tokens\_total\]/1000J\(\\epsilon,K\_\{\\max\}\)=\\mathbb\{E\}\[\\mathrm\{ok\}\]\-0\.02\\,\\mathbb\{E\}\[\\text\{tokens\\\_total\}\]/1000, wheretokens\_totalis the model\-reported tokens for the final generation plus the synthetic clarification costs\. We score on 24 training tasks and evaluate on 24 held out tasks\. The best setting isϵ⋆=0\.01\\epsilon^\{\\star\}=0\.01andKmax⋆=2K\_\{\\max\}^\{\\star\}=2, reaching0\.3750\.375compliance at about219219tokens per task \(vs\.baselineat0\.04170\.0417compliance and about112112tokens\)\.

Summary and takeaways\.We study how to spend a limited token budget between clarifying turns and a final completion when the style is hidden, answers to fixed clarification templates are truthful, and when success is measured by a deterministic verifier\. Policies that ask targeted clarifications improve verifier pass rates relative to asking none, showing that paying for a small number of well chosen questions can be worthwhile, but only when those questions buy information the final output will actually be judged on\.

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/prompt_clarifications_hist_updated.png)\(a\)Clarifications used
![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/prompt_token_ecdf_updated.png)\(b\)Total token ECDF
![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/prompt_efficiency_frontier_largefonts.png)\(c\)Compliance versus average tokens

Figure 4:Prompt autocompletion on 48 synthetic product tasks withϵ=0\.02\\epsilon=0\.02andKmax=3K\_\{\\max\}=3\. Panels show clarification counts by policy, the ECDF of total tokens per task, and verifier pass rate versus average tokens\.active\_weightedimproves compliance at a modest token cost relative tobaselineandrandom, whileask\_allspends the most tokens\.
## 8Automated Prompt Optimization

In this second prompt experiment, the model never asks the user follow\-up questions, but rather treats the choice of system prompt as an online decision problem under a fixed token budget, aiming to quickly identify which prompt variant yields the most reliable multiple\-choice answers\. We fix a small libraryPPof candidate system prompts:letter​\_​only\\mathrm\{letter\\\_only\},short​\_​reasoning\\mathrm\{short\\\_reasoning\},eliminate​\_​two\\mathrm\{eliminate\\\_two\},keyword​\_​match\\mathrm\{keyword\\\_match\},units​\_​and​\_​scales\\mathrm\{units\\\_and\\\_scales\}, andcontrastive​\_​explanations\\mathrm\{contrastive\\\_explanations\}\. At training stepttwe select a promptpt∈Pp\_\{t\}\\in P, format one ARC\-Challenge questionClarket al\.\([2018](https://arxiv.org/html/2608.19202#bib.bib11)\)using a fixed user\-message template, and query the base model once withtemperature=0so the output is deterministic given the prompt\. From the response we extract the first standalone letter in\{A,B,C,D\}\\\{\\texttt\{A\},\\texttt\{B\},\\texttt\{C\},\\texttt\{D\}\\\}, score it as correct or incorrect to obtainyt∈\{0,1\}y\_\{t\}\\in\\\{0,1\\\}, and record the token costτt\\tau\_\{t\}\.

Each promptppis modeled as a Bernoulli arm with unknown accuracyθp\\theta\_\{p\}, and we maintain independent Beta posteriorsθp∼Beta​\(αp,βp\)\\theta\_\{p\}\\sim\\mathrm\{Beta\}\(\\alpha\_\{p\},\\beta\_\{p\}\)initialized atαp=βp=1\\alpha\_\{p\}=\\beta\_\{p\}=1\. After observingyty\_\{t\}for the chosen promptptp\_\{t\}, we update only that prompt viaαpt←αpt\+yt\\alpha\_\{p\_\{t\}\}\\leftarrow\\alpha\_\{p\_\{t\}\}\+y\_\{t\}andβpt←βpt\+1−yt\\beta\_\{p\_\{t\}\}\\leftarrow\\beta\_\{p\_\{t\}\}\+1\-y\_\{t\}, and report the posterior mean𝔼​\[θp\]=αp/\(αp\+βp\)\\mathbb\{E\}\[\\theta\_\{p\}\]=\\alpha\_\{p\}/\(\\alpha\_\{p\}\+\\beta\_\{p\}\)\.

To summarize uncertainty about which prompt is truly best, we defineP⋆=arg⁡maxp⁡θpP^\{\\star\}=\\arg\\max\_\{p\}\\theta\_\{p\}and estimate the induced distribution overP⋆P^\{\\star\}by Monte Carlo sampling, where we draw oneθp\\theta\_\{p\}from each Beta factor and take the maximizing prompt for each draw\. From this empirical distribution we compute an entropyH​\(P⋆\)H\(P^\{\\star\}\)in bits, and after each training step we log the realized entropy dropΔ​Ht=max⁡\{Hbefore−Hafter,0\}\\Delta H\_\{t\}=\\max\\\{H\_\{\\text\{before\}\}\-H\_\{\\text\{after\}\},0\\\}along with an information\-efficiency measureIE1​k​\(t\)=1000​Δ​Ht/τt,\\mathrm\{IE\}\_\{1\\mathrm\{k\}\}\(t\)=1000\\,\\Delta H\_\{t\}/\\tau\_\{t\},which can be read as the entropy reduction achieved per thousand tokens spent on that step\.

Prompt selection is handled by an outer\-loop policy that choosesptp\_\{t\}each step\. Round robin cycles through prompts, Thompson sampling drawsθ~p\\tilde\{\\theta\}\_\{p\}from each posterior and picks the largest, KG chooses the prompt with the highest expected one\-step gain in the current best posterior\-mean accuracy, MI chooses the prompt with the largest expected reduction inH​\(P⋆\)H\(P^\{\\star\}\), and EFE blends MI and KG with a linearly decaying epistemic weight to shift from exploration to exploitation\. Since prompts can differ in response length, MI, KG, and EFE normalize their scores by a per\-prompt token\-cost estimate tracked with an exponential moving average ofτt\\tau\_\{t\}\. Training stops at 400 questions orB=120,000B=120\{,\}000tokens\. In[Figure˜5](https://arxiv.org/html/2608.19202#S8.F5)the 400\-question cap binds \(about5×1045\\times 10^\{4\}tokens\), after which we select the prompt with the highest posterior mean and evaluate it on a shared validation subset\. KG tends to concentrate queries early, leaving rarely tested prompts near the 0\.5 prior mean, while MI and EFE are often most informative early and Thompson sampling and round robin spread learning more evenly\.

![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/promptopt_posteriors.png)\(a\)Posterior mean accuracies
![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/promptopt_ie_updated.png)\(b\)Information gain per 1k tokens
![Refer to caption](https://arxiv.org/html/2608.19202v1/figs/prompt_opt_uncertainity.png)\(c\)Entropy of best\-prompt identity

Figure 5:Automated prompt optimization under a token budget\. Panels show final posterior mean accuracies, realized information gain per 1,000 tokens, and posterior entropy over the identity of the best prompt\. Policies that reduce uncertainty early can avoid committing too soon\.Summary and takeaways\.We treat system\-prompt choice as an online decision problem under a fixed token budget, using repeated, automatically scored trials to update which prompt variant looks best\. The main lesson is to use early trials to reduce uncertainty rather than commit too soon, then choose the variant with the strongest track record under the same scoring rule used throughout training\.

## 9Limitations and Discussion

This paper intentionally studies restricted forms of context acquisition\. In OQA, the AI assistant must identify a hidden item by asking about entries in a fixed attribute table\. We test both yes–no tables and tables where answers take a small set of named values \(Sections[5](https://arxiv.org/html/2608.19202#S5)and[6](https://arxiv.org/html/2608.19202#S6)\)\. The advantage is precision: after each question, we can say exactly how many items remain valid, and we can compare the model to a best\-possible strategy under the same rules\. The cost is realism\. Real conversations may include vague replies, new constraints, contradictory preferences, missing files, and evidence that does not fit a prewritten attribute list\. A stricter future benchmark would allow free\-form questions and ground answers in richer inputs, including images and compositional attributes, for example, CLEVR\-style scenes\(Johnsonet al\.,[2017](https://arxiv.org/html/2608.19202#bib.bib1)\)\.

The current experiments cover three real attribute tables \(Places, Cars, Animals\), larger synthetic multiway attribute tables up to 300 items, and two token\-budget studies on how to spend limited tokens \(Sections[7](https://arxiv.org/html/2608.19202#S7)and[8](https://arxiv.org/html/2608.19202#S8)\)\. This is enough to test the central accounting principle, but not enough to claim a complete agent benchmark\. We leave out temporal reasoning, multimodal perception, robotics, open\-ended tool\-use, and multi\-user collaboration, all of which make context acquisition harder\(Mirzaet al\.,[2016](https://arxiv.org/html/2608.19202#bib.bib2); Lanilloset al\.,[2021](https://arxiv.org/html/2608.19202#bib.bib3)\)\.

We also turn off tools on purpose\. We disable retrieval, function calls, and scratchpads so we can measure what the model can do on its own\(Lewiset al\.,[2020](https://arxiv.org/html/2608.19202#bib.bib4); Schicket al\.,[2023](https://arxiv.org/html/2608.19202#bib.bib5); Nyeet al\.,[2022](https://arxiv.org/html/2608.19202#bib.bib6)\)\. In real products, tools do a lot of the heavy lifting\. They can store the candidate list, filter it exactly, keep memory across turns, and call external systems\. A tool\-enabled version of the benchmark would test whether the agent asks for the right missing information before invoking a tool, instead of hallucinating missing arguments or making premature calls\.

There is also a scaling issue with the oracle we use for comparison\. Our dynamic program gives the best strategy under our rules, but as the number of items grows, the number of different remaining sets that can appear may explode\. It is manageable for the tiers we release, but it will not stay manageable forever\. For larger tasks, approximate baselines based on sampling, search, or learned lookahead will be needed\(Kirschet al\.,[2019](https://arxiv.org/html/2608.19202#bib.bib30); Schrittwieseret al\.,[2020](https://arxiv.org/html/2608.19202#bib.bib7)\)\. More broadly, a locally good question is not always part of the best overall plan\. This is why we report a DP oracle where possible rather than treating greedy information gain as the final answer\.

The two token\-budget studies are controlled demonstrations, not full replicas of real workflows\. In prompt autocompletion \(Section[7](https://arxiv.org/html/2608.19202#S7)\), the assistant chooses among fixed clarifications, and answers are simulated from a hidden style choice\. This isolates whether the assistant asks about the right variables, but it does not test natural phrasing, unclear answers, user impatience, or changing preferences\. In automated prompt optimization \(Section[8](https://arxiv.org/html/2608.19202#S8)\), we pick from a small handwritten set of prompt variants and test them on a multiple\-choice benchmark\. This is clean and automatically scored, but real prompt libraries are larger, correlated, task\-dependent, and often judged by softer preferences\. Token costs can also change across deployments\. Since we evaluate frontier models through hosted APIs, model updates can affect reproducibility\.

Finally, efficient context acquisition is dual use\. The same machinery that helps an assistant ask fewer and better questions can help a malicious actor collect sensitive details, profile users, or probe hidden system rules\. We discuss these connections in the appendix, but we do not test attacks or defenses\. Deployment should pair information\-gain objectives with limits on sensitive follow\-ups, rate limits, audit trails, consent for personal data collection, and privacy\-aware safeguards\(Huanget al\.,[2024](https://arxiv.org/html/2608.19202#bib.bib8); Charleset al\.,[2024](https://arxiv.org/html/2608.19202#bib.bib9); Freibergeret al\.,[2025](https://arxiv.org/html/2608.19202#bib.bib10)\)\.

## 10Conclusion and Future Work

We presented active inference as a context\-acquisition layer for AI agents\. The central decision is whether to act with the current context or spend tokens, interaction, or computation to acquire more evidence\. The bilevel formulation separates the posterior update caused by a hypothetical observation from the outer decision that chooses the next context action or task action\. OQA makes this decision measurable through exact posteriors and a dynamic programming oracle\. Across tiers, frontier models reduce uncertainty each turn but still ask more questions than the oracle\. The two token\-budget studies show the same principle in prompting: a small amount of targeted clarification or prompt experimentation can improve final success when it buys decision\-relevant information\.

Future work should move beyond fixed tables to noisy, open\-ended, and multimodal interaction\. It should also scale oracle baselines with sampling\-based search, evaluate tool\-enabled agents with memory, and integrate explicit stopping decisions\. A central open direction is to make context acquisition safe by design: the agent should learn what it needs to know, but not overcollect information that is irrelevant, sensitive, or unsafe to request\.

## Impact Statement

This paper advances machine learning methods for deciding when an interactive system should acquire more context versus act, using active inference, information gain, and controlled oracle diagnostics\. Potential benefits include fewer unnecessary questioning turns, lower token and compute cost, better tool\-use reliability, and improved task success under ambiguity\.

Risks are that more efficient context acquisition can be misused to extract sensitive information, enable profiling, or speed up adversarial probing of system defenses\. OQA itself uses synthetic data and simulated answers, so it does not require collecting personal data\. In deployment, mitigation includes limiting and auditing follow\-ups, obtaining consent for personal data collection, and adding explicit privacy and safety constraints to the objective\.

## References

- Extensions of generalized binary search to group identification and exponential costs\.InAdvances in Neural Information Processing Systems 23,pp\. 154–162\.Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- M\. Bloodgood and K\. Vijay\-Shanker \(2009\)A method for stopping active learning based on stabilizing predictions and the need for user\-adjustable stopping\.InProceedings of the Thirteenth Conference on Computational Natural Language Learning \(CoNLL 2009\),pp\. 39–47\.External Links:[Link](https://aclanthology.org/W09-1107/)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.p2.1)\.
- K\. Chaloner and I\. Verdinelli \(1995\)Bayesian experimental design: a review\.Statistical Science10\(3\),pp\. 273–304\.External Links:[Document](https://dx.doi.org/10.1214/ss/1177009939)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.p2.1)\.
- Z\. Charles, A\. Ganesh, R\. McKenna, H\. B\. McMahan, N\. Mitchell, K\. Pillutla, and K\. Rush \(2024\)Fine\-tuning large language models with user\-level differential privacy\.arXiv preprint arXiv:2407\.07737\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2407.07737)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p6.1)\.
- D\. Choudhury, S\. Williamson, A\. Golinski, N\. Miao, F\. Bickford Smith, M\. Kirchhof, Y\. Zhang, and T\. Rainforth \(2025\)BED\-LLM: intelligent information gathering with LLMs and bayesian experimental design\.External Links:2508\.21184,[Link](https://arxiv.org/abs/2508.21184)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p1.1)\.
- P\. Clark, I\. Cowhey, O\. Etzioni, T\. Khot, A\. Sabharwal, C\. Schoenick, and O\. Tafjord \(2018\)Think you have solved question answering? try arc, the ai2 reasoning challenge\.arXiv preprint arXiv:1803\.05457\.Cited by:[§8](https://arxiv.org/html/2608.19202#S8.p1.12)\.
- B\. Colson, P\. Marcotte, and G\. Savard \(2007\)An overview of bilevel optimization\.Annals of Operations Research153\(1\),pp\. 235–256\.External Links:[Document](https://dx.doi.org/10.1007/s10479-007-0176-2)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- M\. Cullen, B\. Davey, K\. J\. Friston, and R\. J\. Moran \(2018\)Active inference in OpenAI gym: a paradigm for computational investigations into psychiatric illness\.Biological Psychiatry: Cognitive Neuroscience and Neuroimaging3\(9\),pp\. 809–818\.External Links:[Document](https://dx.doi.org/10.1016/j.bpsc.2018.06.010)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- M\. Cullen, J\. Monney, M\. B\. Mirza, and R\. Moran \(2020\)A meta\-bayesian model of intentional visual search\.arXiv preprint arXiv:2006\.03531\.External Links:[Link](https://arxiv.org/abs/2006.03531)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- L\. Franceschi, P\. Frasconi, S\. Salzo, R\. Grazzi, and M\. Pontil \(2018\)Bilevel programming for hyperparameter optimization and meta\-learning\.InProceedings of the 35th International Conference on Machine Learning \(ICML\),Proceedings of Machine Learning Research, Vol\.80,pp\. 1568–1577\.External Links:[Link](https://proceedings.mlr.press/v80/franceschi18a.html)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- V\. Freiberger, A\. Fleig, and E\. Buchmann \(2025\)"You don’t need a university degree to comprehend data protection this way": LLM\-Powered Interactive Privacy Policy Assessment\.InExtended Abstracts of the CHI Conference on Human Factors in Computing Systems \(CHI EA ’25\),New York, NY, USA\.External Links:[Document](https://dx.doi.org/10.1145/3706599.3719816)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p6.1)\.
- K\. J\. Friston, T\. H\. FitzGerald, F\. Rigoli, P\. Schwartenbeck, and G\. Pezzulo \(2017\)Active inference: a process theory\.Neural Computation29\(1\),pp\. 1–49\.Cited by:[Appendix G](https://arxiv.org/html/2608.19202#A7.p3.11),[§2](https://arxiv.org/html/2608.19202#S2.p1.1)\.
- R\. Haertel, E\. Ringger, K\. Seppi, J\. Carroll, and P\. McClanahan \(2008\)Assessing the costs of sampling methods in active learning for annotation\.InProceedings of ACL\-08: HLT Short Papers,pp\. 65–68\.External Links:[Link](https://aclanthology.org/P08-2017/)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.p2.1)\.
- P\. Hennig and C\. J\. Schuler \(2012\)Entropy search for information\-efficient global optimization\.Journal of Machine Learning Research13,pp\. 1809–1837\.External Links:[Link](https://jmlr.org/papers/v13/hennig12a.html)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.p2.1)\.
- N\. Houlsby, F\. Huszár, Z\. Ghahramani, and M\. Lengyel \(2011\)Bayesian active learning for classification and preference learning\.External Links:1112\.5745,[Link](https://arxiv.org/abs/1112.5745)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.p2.1)\.
- R\. Houthooft, X\. Chen, Y\. Duan, J\. Schulman, F\. De Turck, and P\. Abbeel \(2016\)VIME: variational information maximizing exploration\.InAdvances in Neural Information Processing Systems 29,pp\. 1109–1117\.External Links:[Link](https://papers.nips.cc/paper_files/paper/2016/hash/abd815286ba1007abfbb8415b83ae2cf-Abstract.html)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- Z\. Hu, C\. Liu, X\. Feng, Y\. Zhao, S\. Ng, A\. T\. Luu, J\. He, P\. W\. Koh, and B\. Hooi \(2024\)Uncertainty of thoughts: uncertainty\-aware planning enhances information seeking in large language models\.External Links:2402\.03271,[Link](https://arxiv.org/abs/2402.03271)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p1.1)\.
- K\. Huang, B\. Chen, Y\. Lu, S\. Wu, D\. Wang, Y\. Huang, H\. Jiang, Z\. Zhou, J\. Cao, and X\. Peng \(2024\)Lifting the veil on composition, risks, and mitigations of the large language model supply chain\.arXiv preprint arXiv:2410\.21218\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2410.21218)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p6.1)\.
- B\. Jedynak, P\. I\. Frazier, and R\. Sznitman \(2012\)Twenty questions with noise: bayes optimal policies for entropy loss\.Journal of Applied Probability49\(1\),pp\. 114–136\.External Links:[Document](https://dx.doi.org/10.1239/jap/1331216837)Cited by:[§1](https://arxiv.org/html/2608.19202#S1.p3.4),[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- J\. Johnson, B\. Hariharan, L\. van der Maaten, F\. Li, C\. L\. Zitnick, and R\. Girshick \(2017\)CLEVR: a diagnostic dataset for compositional language and elementary visual reasoning\.InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition \(CVPR\),pp\. 1988–1997\.External Links:[Document](https://dx.doi.org/10.1109/CVPR.2017.215)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p1.1)\.
- A\. Kirsch, J\. van Amersfoort, and Y\. Gal \(2019\)BatchBALD: efficient and diverse batch acquisition for deep bayesian active learning\.InAdvances in Neural Information Processing Systems,External Links:[Link](https://arxiv.org/abs/1906.08158)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p4.1)\.
- K\. Kobalczyk, N\. Astorga, T\. Liu, and M\. van der Schaar \(2025\)Active task disambiguation with llms\.External Links:2502\.04485,[Link](https://arxiv.org/abs/2502.04485)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p1.1)\.
- P\. Lanillos, C\. Meo, C\. Pezzato, A\. A\. Meera, M\. Baioumy, W\. Ohata, A\. Tschantz, B\. Millidge, M\. Wisse, C\. L\. Buckley, and J\. Tani \(2021\)Active inference in robotics and artificial agents: survey and challenges\.arXiv preprint arXiv:2112\.01871\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2112.01871)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p2.1)\.
- S\. Levine \(2018\)Reinforcement learning and control as probabilistic inference: tutorial and review\.arXiv preprint arXiv:1805\.00909\.External Links:1805\.00909,[Link](https://arxiv.org/abs/1805.00909)Cited by:[§1](https://arxiv.org/html/2608.19202#S1.p5.1),[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px2.p1.1)\.
- P\. Lewis, E\. Perez, A\. Piktus, F\. Petroni, V\. Karpukhin, N\. Goyal, H\. Küttler, M\. Lewis, W\. Yih, T\. Rocktäschel, S\. Riedel, and D\. Kiela \(2020\)Retrieval\-augmented generation for knowledge\-intensive NLP tasks\.InAdvances in Neural Information Processing Systems,Vol\.33,pp\. 9459–9474\.External Links:[Document](https://dx.doi.org/10.5555/3495724.3496517)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p3.1)\.
- D\. V\. Lindley \(1956\)On a measure of the information provided by an experiment\.The Annals of Mathematical Statistics27\(4\),pp\. 986–1005\.External Links:[Document](https://dx.doi.org/10.1214/aoms/1177728069)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.p2.1)\.
- G\. Liu, Y\. Qu, J\. Schneider, A\. Singh, and A\. Kumar \(2025\)CaRT: teaching LLM agents to know when they know enough\.External Links:2510\.08517,[Link](https://arxiv.org/abs/2510.08517)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p1.1)\.
- B\. Millidge, A\. Seth, and C\. L\. Buckley \(2021\)Understanding the origin of information\-seeking exploration in probabilistic objectives for control\.arXiv preprint arXiv:2103\.06859\.External Links:2103\.06859,[Link](https://arxiv.org/abs/2103.06859)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px2.p1.1)\.
- B\. Millidge, A\. Tschantz, A\. K\. Seth, and C\. L\. Buckley \(2020\)On the relationship between active inference and control as inference\.InActive Inference,Communications in Computer and Information Science, Vol\.1326,pp\. 3–11\.External Links:[Document](https://dx.doi.org/10.1007/978-3-030-64919-7%5F1)Cited by:[§1](https://arxiv.org/html/2608.19202#S1.p5.1),[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px2.p1.1)\.
- B\. Millidge \(2021\)Applications of the free energy principle to machine learning and neuroscience\.Note:PhD thesis, arXiv:2107\.00140External Links:2107\.00140,[Link](https://arxiv.org/abs/2107.00140)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px2.p1.1)\.
- B\. Millidge \(2024\)A retrospective on active inference\.Note:[https://www\.beren\.io/2024\-07\-27\-A\-Retrospective\-on\-Active\-Inference/](https://www.beren.io/2024-07-27-A-Retrospective-on-Active-Inference/)Blog post, posted July 27, 2024Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px2.p1.1)\.
- M\. B\. Mirza, R\. A\. Adams, C\. D\. Mathys, and K\. J\. Friston \(2016\)Scene construction, visual foraging, and active inference\.Frontiers in Computational Neuroscience10,pp\. 56\.External Links:[Document](https://dx.doi.org/10.3389/fncom.2016.00056)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p2.1)\.
- R\. D\. Nowak \(2011\)The geometry of generalized binary search\.IEEE Transactions on Information Theory57\(12\),pp\. 7893–7906\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2011.2169298),[Link](https://doi.org/10.1109/TIT.2011.2169298)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- R\. Nowak \(2009\)Noisy generalized binary search\.InAdvances in Neural Information Processing Systems 22,pp\. 1366–1374\.Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- M\. Nye, A\. J\. Andreassen, G\. Gur\-Ari, H\. Michalewski, J\. Austin, D\. Bieber, D\. Dohan, A\. Lewkowycz, M\. Bosma, D\. Luan, C\. Sutton, and A\. Odena \(2022\)Show your work: scratchpads for intermediate computation with language models\.InInternational Conference on Learning Representations \(ICLR\),External Links:[Link](https://openreview.net/forum?id=iedYJm92o0a)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p3.1)\.
- T\. Parr and K\. J\. Friston \(2019\)Generalised free energy and active inference\.Biological Cybernetics113,pp\. 495–513\.Cited by:[Appendix G](https://arxiv.org/html/2608.19202#A7.p3.11),[§2](https://arxiv.org/html/2608.19202#S2.p1.1)\.
- D\. Pathak, P\. Agrawal, A\. A\. Efros, and T\. Darrell \(2017\)Curiosity\-driven exploration by self\-supervised prediction\.InProceedings of the 34th International Conference on Machine Learning \(ICML\),Proceedings of Machine Learning Research, Vol\.70,pp\. 2778–2787\.External Links:[Link](https://proceedings.mlr.press/v70/pathak17a.html)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- W\. T\. Piriyakulkij, V\. Kuleshov, and K\. Ellis \(2023\)Active preference inference using language models and probabilistic reasoning\.External Links:2312\.12009,[Link](https://arxiv.org/abs/2312.12009)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Prakash, N\. He, D\. Goktas, and A\. Greenwald \(2025\)Bi\-level policy optimization with nyström hypergradients\.CoRRabs/2505\.11714\.External Links:2505\.11714,[Link](https://arxiv.org/abs/2505.11714)Cited by:[Appendix G](https://arxiv.org/html/2608.19202#A7.p5.5)\.
- T\. Rainforth, A\. Foster, D\. R\. Ivanova, and F\. Bickford Smith \(2024\)Modern bayesian experimental design\.Statistical Science39\(1\),pp\. 100–114\.Cited by:[§2](https://arxiv.org/html/2608.19202#S2.p2.1)\.
- D\. Russo and B\. Van Roy \(2014\)Learning to optimize via information\-directed sampling\.Advances in neural information processing systems27\.Cited by:[§2](https://arxiv.org/html/2608.19202#S2.p2.1)\.
- T\. Schick, J\. Dwivedi\-Yu, R\. Dessì, R\. Raileanu, M\. Lomeli, E\. Hambro, L\. Zettlemoyer, N\. Cancedda, and T\. Scialom \(2023\)Toolformer: language models can teach themselves to use tools\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 68539–68551\.External Links:[Document](https://dx.doi.org/10.5555/3666122.3669119)Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p3.1)\.
- J\. Schrittwieser, I\. Antonoglou, T\. Hubert, K\. Simonyan, L\. Sifre, S\. Schmitt, A\. Guez, E\. Lockhart, D\. Hassabis, T\. Graepel, T\. Lillicrap, and D\. Silver \(2020\)Mastering atari, go, chess and shogi by planning with a learned model\.Nature588\(7839\),pp\. 604–609\.External Links:[Document](https://dx.doi.org/10.1038/s41586-020-03051-4),1911\.08265Cited by:[§9](https://arxiv.org/html/2608.19202#S9.p4.1)\.
- H\. Shen, Z\. Yang, and T\. Chen \(2024\)Principled penalty\-based methods for bilevel reinforcement learning and RLHF\.Note:Shorter version accepted to ICML 2024External Links:2402\.06886,[Link](https://arxiv.org/abs/2402.06886)Cited by:[Appendix G](https://arxiv.org/html/2608.19202#A7.p2.9)\.
- T\. Shin, Y\. Razeghi, R\. L\. Logan, E\. Wallace, and S\. Singh \(2020\)AutoPrompt: eliciting knowledge from language models with automatically generated prompts\.InProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),External Links:[Link](https://aclanthology.org/2020.emnlp-main.346/)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.
- V\. Thoma, B\. Pasztor, A\. Krause, G\. Ramponi, and Y\. Hu \(2024\)Contextual bilevel reinforcement learning for incentive alignment\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 127369–127435\.External Links:[Link](https://papers.nips.cc/paper_files/paper/2024/hash/e66309ead63bc1410d2df261a28f602d-Abstract-Conference.html)Cited by:[Appendix G](https://arxiv.org/html/2608.19202#A7.p2.9)\.
- W\. Wang, J\. Shi, Z\. Ling, Y\. Chan, C\. Wang, C\. Lee, Y\. Yuan, J\. Huang, W\. Jiao, and M\. R\. Lyu \(2024\)Learning to ask: when llm agents meet unclear instruction\.External Links:2409\.00557,[Link](https://arxiv.org/abs/2409.00557)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p1.1)\.
- T\. Zhang, P\. Qin, Y\. Deng, C\. Huang, W\. Lei, J\. Liu, D\. Jin, H\. Liang, and T\. Chua \(2024\)CLAMBER: a benchmark of identifying and clarifying ambiguous information needs in large language models\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics,External Links:[Link](https://aclanthology.org/2024.acl-long.578/)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p1.1)\.
- Y\. Zhou, A\. I\. Muresanu, Z\. Han, K\. Paster, S\. Pitis, H\. Chan, and J\. Ba \(2023\)Large language models are human\-level prompt engineers\.InInternational Conference on Learning Representations \(ICLR\),External Links:[Link](https://openreview.net/forum?id=92gvk82DE-)Cited by:[§2](https://arxiv.org/html/2608.19202#S2.SS0.SSS0.Px1.p2.1)\.

## Appendix AOptimal Question Asking: API Transcripts and Prompt Templates

OQA is scored from the transcript alone\. At each turn, the model asks about exactly one named attribute\. The oracle returns the answer by looking it up in a finite table of attributes\. After the reply, a scoring script filters the remaining setCtC\_\{t\}by exact consistency\. Because every step is deterministic, the score is fully reproducible\. With the same prompt and the same hidden target, replaying the same message sequence yields the sameCtC\_\{t\}, the same entropyHt=log2⁡\|Ct\|H\_\{t\}=\\log\_\{2\}\|C\_\{t\}\|, and the same stopping time\.

The protocol enforces two rules\. Every question must use an attribute name from a fixed list\. Each turn may refer to only one attribute\. In binary OQA, the oracle replies"Yes"or"No", and the update isCt\+1=\{x∈Ct∣zj​\(x\)=ot\}C\_\{t\+1\}=\\\{x\\in C\_\{t\}\\mid z\_\{j\}\(x\)=o\_\{t\}\\\}\. In multiway OQA, the oracle replies with a single value string, and the update isCt\+1=\{x∈Ct∣at​\(x\)=ot\}C\_\{t\+1\}=\\\{x\\in C\_\{t\}\\mid a\_\{t\}\(x\)=o\_\{t\}\\\}\. A run ends when\|Ct\|=1\|C\_\{t\}\|=1\. It can also end earlier when the remaining items share the same vector of attributes, so no allowed query can split them further\. For reliable parsing, a strict JSON format is available\. The next query is read from the"question"field, while any extra fields are ignored and may be used for debugging\.

`Binary OQA user prompt template \(plain\-text mode\) Binary OQA placeholder instantiations \(domain families\) The concrete attribute list <ATTRIBUTE\_1\.\.d\> is provided in each dataset’s data/attributes\.txt\. Binary OQA sample transcript \(2 turns shown\) System\. You are a careful planner\. User\. This is a PLACES attributes dataset\. I have a hidden place in mind\. Ask only yes/no questions about one attribute at a time from the provided list\. Assistant \(Turn 1\)\. Question: Is it coastal? Belief \(before the answer\): uniform over all 25 places\. Uncertainty: H0=log2⁡25≈4\.64H\_\{0\}=\\log\_\{2\}25\\approx 4\.64 bits\. Stop: no\. User\. No\. Assistant \(Turn 2\)\. Update: filter to candidates with coastal = false\. Remaining candidates: 9 places \(uniform over the remaining set\)\. Uncertainty: H1=log2⁡9≈3\.17H\_\{1\}=\\log\_\{2\}9\\approx 3\.17 bits\. Next question: Is it mountainous? User\. Yes\. Multiway \(kk\-ary\) user prompt template \(plain\-text mode\) Multiway \(kk\-ary\) sample transcript \(2 turns shown\) System\. You are a careful planner\. User\. This is a kk\-ary attributes dataset with 200 abstract objects\. Ask about exactly one attribute per turn from: color, shape, material, size, pattern, origin, use\_case, energy\. Each answer will be a single value \(e\.g\., "red"\)\. Assistant \(Turn 1\)\. Question: What is the energy? Belief \(before the answer\): uniform over all 200 items\. Uncertainty: H0=log2⁡200≈7\.64H\_\{0\}=\\log\_\{2\}200\\approx 7\.64 bits\. Stop: no\. User\. electric Assistant \(Turn 2\)\. Update: filter to candidates with energy = electric\. Remaining candidates: \(uniform over the filtered set\)\. Uncertainty: H1≈3\.12H\_\{1\}\\approx 3\.12 bits\. Next question: What is the shape? User\. hexagon`

`Appendix B Exact Dynamic Programming Oracle The oracle curves in our figures are produced by an exact planner that minimizes the expected number of questions required to identify the hidden target under a uniform prior and deterministic answers\. In these tiers, each reply removes every candidate that is inconsistent with it, so the posterior after any transcript is uniform over the remaining candidates\. The belief state is therefore completely determined by the current candidate set C⊆𝒳C\\subseteq\\mathcal\{X\}\. Asking one attribute partitions CC into subsets indexed by the possible replies, and the next belief is obtained by restricting to the subset that matches the observed reply\. This reduces optimal question asking to a finite decision problem over sets, with termination when \|C\|≤1\|C\|\\leq 1 or when the allowed attributes cannot further separate the remaining items\. Let CC be the current candidate set\. A query q∈𝒬q\\in\\mathcal\{Q\} induces a set of possible replies ℛ​\(q,C\)\\mathcal\{R\}\(q,C\) and corresponding next candidate sets \{Cr\}r∈ℛ​\(q,C\)\\\{C\_\{r\}\\\}\_\{r\\in\\mathcal\{R\}\(q,C\)\}, where Cr=\{x∈C∣q​\(x\)=r\}C\_\{r\}=\\\{x\\in C\\mid q\(x\)=r\\\}\. Under a uniform posterior on CC and deterministic replies, Pr⁡\[r\]=\|Cr\|/\|C\|\\Pr\[r\]=\|C\_\{r\}\|/\|C\|\. Define Cost​\(C\)\\mathrm\{Cost\}\(C\) as the optimal expected number of additional questions until termination, starting from CC\. A set is terminal when \|C\|≤1\|C\|\\leq 1 or when every query fails to split CC into at least two nonempty subsets\. Bellman optimality gives the recursion Cost​\(C\)=minq∈𝒬\|ℛ​\(q,C\)\|≥2⁡\(1\+∑r∈ℛ​\(q,C\)\|Cr\|\|C\|​Cost​\(Cr\)\),Cost​\(C\)=0​if C is terminal\.\\mathrm\{Cost\}\(C\)=\\min\_\{\\begin\{subarray\}\{c\}q\\in\\mathcal\{Q\}\\\\ \|\\mathcal\{R\}\(q,C\)\|\\geq 2\\end\{subarray\}\}\\left\(1\+\\sum\_\{r\\in\\mathcal\{R\}\(q,C\)\}\\frac\{\|C\_\{r\}\|\}\{\|C\|\}\\,\\mathrm\{Cost\}\(C\_\{r\}\)\\right\),\\qquad\\mathrm\{Cost\}\(C\)=0\\ \\text\{if $C$ is terminal\}\. \(19\) The oracle policy at state CC is the minimizer in \(19\)\. Greedy maximization of one step expected information gain optimizes only the immediate entropy drop, while \(19\) is optimal for the expected remaining number of questions\. In the binary tiers, each query is an index j∈\[d\]j\\in\[d\] with replies in \{0,1\}\\\{0,1\\\}\. Writing Cyes=\{x∈C∣zj​\(x\)=1\}C^\{\\text\{yes\}\}=\\\{x\\in C\\mid z\_\{j\}\(x\)=1\\\} and Cno=C∖CyesC^\{\\text\{no\}\}=C\\setminus C^\{\\text\{yes\}\}, the recursion becomes Cost​\(C\)=minj∈\[d\]Cyes≠∅Cno≠∅⁡\(1\+\|Cyes\|\|C\|​Cost​\(Cyes\)\+\|Cno\|\|C\|​Cost​\(Cno\)\),\\mathrm\{Cost\}\(C\)=\\min\_\{\\begin\{subarray\}\{c\}j\\in\[d\]\\\\ C^\{\\text\{yes\}\}\\neq\\emptyset\\\\ C^\{\\text\{no\}\}\\neq\\emptyset\\end\{subarray\}\}\\left\(1\+\\frac\{\|C^\{\\text\{yes\}\}\|\}\{\|C\|\}\\mathrm\{Cost\}\(C^\{\\text\{yes\}\}\)\+\\frac\{\|C^\{\\text\{no\}\}\|\}\{\|C\|\}\\mathrm\{Cost\}\(C^\{\\text\{no\}\}\)\\right\), \(20\) with Cost​\(C\)=0\\mathrm\{Cost\}\(C\)=0 when \|C\|≤1\|C\|\\leq 1 or when no attribute splits CC\. This is the dynamic program used to construct the optimal expected depth decision tree for the binary oracle\. In the multiway categorical tiers, a query is an attribute a∈𝒜a\\in\\mathcal\{A\} whose reply is a single value v∈𝒱av\\in\\mathcal\{V\}\_\{a\}\. For a candidate set CC define the branches Cv=\{x∈C∣a​\(x\)=v\}C\_\{v\}=\\\{x\\in C\\mid a\(x\)=v\\\}, and ignore values with \|Cv\|=0\|C\_\{v\}\|=0\. If there is only one nonempty branch, then aa does not split CC and is not considered\. Otherwise, Cost​\(C\)=mina∈𝒜\|\{v∈𝒱a∣\|Cv\|\>0\}\|≥2⁡\(1\+∑v∈𝒱a:\|Cv\|\>0\|Cv\|\|C\|​Cost​\(Cv\)\),\\mathrm\{Cost\}\(C\)=\\min\_\{\\begin\{subarray\}\{c\}a\\in\\mathcal\{A\}\\\\ \|\\\{v\\in\\mathcal\{V\}\_\{a\}\\mid\|C\_\{v\}\|\>0\\\}\|\\geq 2\\end\{subarray\}\}\\left\(1\+\\sum\_\{v\\in\\mathcal\{V\}\_\{a\}:\\,\|C\_\{v\}\|\>0\}\\frac\{\|C\_\{v\}\|\}\{\|C\|\}\\,\\mathrm\{Cost\}\(C\_\{v\}\)\\right\), \(21\) with the same terminal condition as above\. The recursion is evaluated over candidate sets\. In practice, repeated subproblems can be avoided by caching Cost​\(C\)\\mathrm\{Cost\}\(C\) keyed by a canonical representation of CC, such as a sorted tuple of item identifiers\. A fixed attribute order yields a reproducible oracle policy when several attributes tie\. To generate the oracle entropy traces used in plots, the optimal policy is rolled out for each fixed target x⋆x^\{\\star\}\. Starting from C0=𝒳C\_\{0\}=\\mathcal\{X\}, at step tt the oracle selects an optimal query for CtC\_\{t\}, reads the target’s true reply, filters to Ct\+1C\_\{t\+1\}, and records Ht=log2⁡\|Ct\|H\_\{t\}=\\log\_\{2\}\|C\_\{t\}\|, with t=0t=0 corresponding to the prior\. The trajectory ends when the set is terminal, so tiers with duplicates can plateau at Ht\>0H\_\{t\}\>0\. Appendix C Scaling Up OQA Arbitrarily With Synthetic Attribute Tables The real object tables used in OQA are small and fixed\. For larger studies, OQA also supports synthetic attribute tables that can be regenerated from a random seed at arbitrary scale\. A synthetic tier is specified by an attribute schema, a candidate count NN, and a seed\. The generator writes the same artifacts as the released tiers\. It outputs a JSON table of item attributes, an attributes\.txt file for binary tiers or a schema description for categorical tiers, an items\.txt list of identifiers, and an equivalence\_classes\.json file that groups items with identical attribute vectors when duplicates are present\. This setup serves two purposes\. It enables scale, since NN can increase without changing the evaluation code or the transcript rules\. It also reduces semantic assistance\. Item identifiers and attribute names can be arbitrary strings, such as hexadecimal keys and short tokens, so performance reflects query choice and consistent set updates rather than world knowledge\. In the binary synthetic tiers, fix NN and choose a Boolean dimension dd such that 2d≥N2^\{d\}\\geq N\. This guarantees that at least NN distinct Boolean vectors exist\. A simple construction samples NN distinct vectors in \{0,1\}d\\\{0,1\\\}^\{d\}, assigns each vector to a fresh identifier, and records the resulting table\. When dd is close to ⌈log2⁡N⌉\\lceil\\log\_\{2\}N\\rceil, the instance lies near the information limit, since an ideal policy needs on the order of log2⁡N\\log\_\{2\}N questions\. Taking dd larger adds redundancy, which tests whether an agent can avoid attributes that do not help separate the remaining candidates\. Controlled ambiguity can be introduced by allowing duplicates, so the stopping rule ends on a nontrivial equivalence class\. In the multiway synthetic tiers, choose a finite attribute set 𝒜\\mathcal\{A\} with value sets \{𝒱a\}a∈𝒜\\\{\\mathcal\{V\}\_\{a\}\\\}\_\{a\\in\\mathcal\{A\}\} such that ∏a∈𝒜\|𝒱a\|≥N\\prod\_\{a\\in\\mathcal\{A\}\}\|\\mathcal\{V\}\_\{a\}\|\\geq N\. This ensures that at least NN distinct categorical vectors exist\. Sample NN distinct vectors from the Cartesian product and map each to a fresh identifier\. Allowing duplicates creates plateaus where several items share the same attribute vector\. Difficulty is controlled by the branching factors \|𝒱a\|\|\\mathcal\{V\}\_\{a\}\|, by how balanced the value frequencies are, and by correlations among attributes\. For semantic domains such as Places, Cars, and Animals, listing the allowed attribute names is often enough, since background knowledge can guide reasonable query orders\. For fully synthetic domains the names carry no meaning, so a planning test typically requires providing the table, or an equivalent compact encoding, in the prompt\. Two convenient encodings are id:bitstring for binary tiers and id:v1,v2,\.\.\. for kk\-ary tiers\. Both grow linearly with NN and remain easy to parse in long context settings\. The transcript\-based metrics, namely CtC\_\{t\} and Ht=log2⁡\|Ct\|H\_\{t\}=\\log\_\{2\}\|C\_\{t\}\|, remain exact for any NN because they rely only on deterministic filtering\. Exact dynamic programming does not scale in the same way\. Its states are candidate subsets, and the number of reachable subsets can grow very quickly as NN increases\. For larger tiers, greedy information gain, shallow lookahead, or sampling\-based planners provide strong approximate baselines, while the benchmark definition remains unchanged\. Deterministic synthetic OQA generator \(binary and kk\-ary, reference implementation sketch\) Appendix D Prompt Autocompletion Experiment: Full Specification Each run in the prompt autocompletion experiment has an unknown style variable, a short clarification phase with fixed question text, a single model call that produces the final description, and a deterministic verifier that scores the result\. The policy controls only which style attribute to query next and when to stop\. Each task provides a product name and three feature phrases\. The latent user intent is U=\(tone,length,format\),U=\(\\text\{tone\},\\text\{length\},\\text\{format\}\), where tone, length, and format each have two listed values\. The prior over UU is uniform and factorized\. A policy may ask up to Kmax≤3K\_\{\\max\}\\leq 3 clarification questions\. Each clarification reveals the true value of exactly one component of UU through a simulated answer\. During belief updates, the implementation models the answer channel with symmetric label noise ε=0\.12\\varepsilon=0\.12\. After the policy stops, a single style estimate U^\\hat\{U\} is chosen by a MAP rule under the current belief\. Ties are broken by argmax returning the first listed label in each attribute’s ordering: formal, short, bullets\. The final description is then generated with exactly one model call conditioned on U^\\hat\{U\}\. The run is scored only by the verifier described below\. The text of each clarification question is fixed, and only the choice of which attribute to ask is controlled by the policy: • tone Before I write, do you prefer a formal or friendly tone? • length Do you want a short or a medium length description? • format Should I present it as bullet points or as a paragraph? Clarification turns are charged a fixed synthetic schedule that approximates the growth of context, clarify\_cost​\(k\)∈\{24,48,72\}for the kth clarification, with k starting at 1\.\\texttt\{clarify\\\_cost\}\(k\)\\in\\\{24,48,72\\\}\\quad\\text\{for the $k$th clarification, with $k$ starting at 1\.\} Total tokens per run are computed as tokens\_total=∑k=1Kclarify\_cost​\(k\)\+tokens\_api,\\texttt\{tokens\\\_total\}=\\sum\_\{k=1\}^\{K\}\\texttt\{clarify\\\_cost\}\(k\)\+\\texttt\{tokens\\\_api\}, where tokens\_api is the model reported total token usage for the single generation call\. The final call sends a single text prompt to the Responses API, using the model gpt\-4o\. The prompt is formatted with two labeled sections, \[System\] and \[User\], as shown below\. The \[System\] section is constant\. The \[User\] section is formed by inserting the task fields and the MAP style U^\\hat\{U\} into the template below\. ⬇ \[System\] You are a concise marketing writer\. Follow tone, format, and length exactly\. Reuse the product features as is\. \[User\] Product: <TASK\.NAME\> Features: <TASK\.FEATURE\_1\>, <TASK\.FEATURE\_2\>, <TASK\.FEATURE\_3\> Tone: <formal\|friendly\> Format: <bullets\|paragraph\> Length: <short\|medium\> Write the description now\. Given the generated text out, the task feature strings, and the latent UU, the output is accepted if and only if all three conditions hold\. First, every feature phrase appears literally as a substring of out after both are lowercased, so the check is f\.lower\(\) in out\.lower\(\) for each feature string f\. Second, the format matches U\.formatU\.\\texttt\{format\}\. If U\.format=bulletsU\.\\texttt\{format\}=\\texttt\{bullets\}, out must contain at least two non empty lines whose first non whitespace character is \-, \*, or \\item\. If U\.format=paragraphU\.\\texttt\{format\}=\\texttt\{paragraph\}, the output is rejected when it contains obvious bullet starts, which is tested by checking whether out contains \\n\-, \\n\*, or \\n\\item\. Third, the length matches U\.lengthU\.\\texttt\{length\}\. Let wc be the number of tokens in out when splitting on whitespace\. If U\.length=shortU\.\\texttt\{length\}=\\texttt\{short\}, require wc≤70\\texttt\{wc\}\\leq 70\. If U\.length=mediumU\.\\texttt\{length\}=\\texttt\{medium\}, require 70≤wc≤16070\\leq\\texttt\{wc\}\\leq 160\. One run can be summarized compactly as follows\. The product is Stainless Steel Bottle, with features insulated, 24 oz, and BPA free\. The latent style is U=\{friendly,short,paragraph\}U=\\\{\\texttt\{friendly\},\\texttt\{short\},\\texttt\{paragraph\}\\\}\. A policy that queries all three attributes receives those three simulated answers, so U^=U\\hat\{U\}=U\. The model is then called once with the template above instantiated by these fields\. The verifier returns PASS if the output contains all three feature substrings, contains no bullet lines, and has word count at most 7070\. Appendix E Prompt Optimization Experiment: Full Specification Prompt optimization is treated as a small Bayesian bandit problem over a fixed set of prompt variants on ARC\-Challenge multiple\-choice questions\. Each training step selects one prompt variant, makes exactly one model call at temperature=0, parses a single answer letter, and logs both correctness and the total token count returned by the API\. Learning occurs only in the bandit state\. The language model itself is not updated\. The base model used in all calls is gpt\-4o\. We load ARC\-Challenge from the Hugging Face AI2 ARC dataset with the ARC\-Challenge configuration\. We filter both the training and validation splits to keep only examples with exactly four answer choices labeled A, B, C, and D\. We reorder the choice texts into that order and drop any example whose answerKey is not one of those four labels\. Fix the set of prompt variants P=\{\\displaystyle P=\\\{ letter\_only,short\_reasoning,\\displaystyle\\texttt\{letter\\\_only\},\\texttt\{short\\\_reasoning\}, eliminate\_two,keyword\_match,\\displaystyle\\texttt\{eliminate\\\_two\},\\texttt\{keyword\\\_match\}, units\_and\_scales,contrastive\_explanations\}\.\\displaystyle\\texttt\{units\\\_and\\\_scales\},\\texttt\{contrastive\\\_explanations\}\\\}\. Each p∈Pp\\in P corresponds to a fixed system prompt\. The user message has a fixed template shared across all variants\. At step tt, the policy chooses pt∈Pp\_\{t\}\\in P, formats one ARC example into the user template, prepends the system prompt for ptp\_\{t\}, and calls the base model once\. The API\-reported total token usage for that call is denoted by τt\\tau\_\{t\}\. User message template shared by all prompts System prompts for the six variants A deterministic checker maps the raw model output at step tt to a binary outcome\. It extracts the first standalone letter in \{A,B,C,D\}\\\{\\texttt\{A\},\\texttt\{B\},\\texttt\{C\},\\texttt\{D\}\\\} using a case\-insensitive word\-boundary match, for example the regex \\b\(\[ABCD\]\)\\b\. If no such letter is found, the step is marked incorrect\. Otherwise the step outcome is yt=1y\_\{t\}=1 if the parsed letter equals the gold answerKey, and yt=0y\_\{t\}=0 otherwise\. All policies train on the same fixed subset of at most 400400 ARC\-Challenge training questions, sampled without replacement using a fixed random seed\. Training stops when this subset is exhausted or when cumulative training tokens reach or exceed a budget BB, with the reference setting B=120,000B=120\{,\}000\. \(Because the budget check happens after each model call, the final total can exceed BB by at most one call\.\) Evaluation uses a shared holdout subset of 200200 ARC\-Challenge validation questions, also sampled once with a fixed seed\. Policy comparisons therefore differ only through the sequence of prompt variants selected during training\. Each prompt p∈Pp\\in P is treated as an arm with an unknown Bernoulli accuracy θp\\theta\_\{p\}\. Independent Beta posteriors are maintained, qt​\(θp\)=Beta​\(αp,βp\),αp=βp=1​at initialization\.q\_\{t\}\(\\theta\_\{p\}\)=\\mathrm\{Beta\}\(\\alpha\_\{p\},\\beta\_\{p\}\),\\qquad\\alpha\_\{p\}=\\beta\_\{p\}=1\\ \\text\{at initialization\}\. After testing ptp\_\{t\} and observing yt∈\{0,1\}y\_\{t\}\\in\\\{0,1\\\}, the conjugate update is αpt←αpt\+yt,βpt←βpt\+\(1−yt\),\\alpha\_\{p\_\{t\}\}\\leftarrow\\alpha\_\{p\_\{t\}\}\+y\_\{t\},\\qquad\\beta\_\{p\_\{t\}\}\\leftarrow\\beta\_\{p\_\{t\}\}\+\(1\-y\_\{t\}\), and the posterior mean accuracy is mp≡𝔼​\[θp\]=αpαp\+βp\.m\_\{p\}\\equiv\\mathbb\{E\}\[\\theta\_\{p\}\]=\\frac\{\\alpha\_\{p\}\}\{\\alpha\_\{p\}\+\\beta\_\{p\}\}\. Token cost affects only acquisition\. Each arm maintains an exponential moving average estimate c^p\\hat\{c\}\_\{p\} of its token cost, initialized at c^p=120\\hat\{c\}\_\{p\}=120 for all prompts\. After an evaluation of ptp\_\{t\} with observed cost τt\\tau\_\{t\}, the update is c^pt←γ​c^pt\+\(1−γ\)​τt,γ=0\.9\.\\hat\{c\}\_\{p\_\{t\}\}\\leftarrow\\gamma\\,\\hat\{c\}\_\{p\_\{t\}\}\+\(1\-\\gamma\)\\,\\tau\_\{t\},\\qquad\\gamma=0\.9\. Let P⋆=arg⁡maxp∈P⁡θpP^\{\\star\}=\\arg\\max\_\{p\\in P\}\\theta\_\{p\} denote the identity of the best prompt under the latent accuracies\. Its posterior is approximated by Monte Carlo sampling\. Draw θ~p\(s\)∼Beta​\(αp,βp\)\\tilde\{\\theta\}\_\{p\}^\{\(s\)\}\\sim\\mathrm\{Beta\}\(\\alpha\_\{p\},\\beta\_\{p\}\) independently for s=1,…,Ss=1,\\dots,S and all p∈Pp\\in P, with the reference choice S=600S=600 during training\. Compute P~⋆\(s\)=arg⁡maxp⁡θ~p\(s\)\\tilde\{P\}^\{\\star\(s\)\}=\\arg\\max\_\{p\}\\tilde\{\\theta\}\_\{p\}^\{\(s\)\} and form the empirical distribution π^t​\(p\)=1S​∑s=1S𝟏​\{P~⋆\(s\)=p\}\.\\hat\{\\pi\}\_\{t\}\(p\)=\\frac\{1\}\{S\}\\sum\_\{s=1\}^\{S\}\\mathbf\{1\}\\\{\\tilde\{P\}^\{\\star\(s\)\}=p\\\}\. Uncertainty is summarized by the entropy in bits Ht≡H​\(P⋆\)≈−∑p∈Pπ^t​\(p\)​log2⁡π^t​\(p\)\.H\_\{t\}\\equiv H\(P^\{\\star\}\)\\approx\-\\sum\_\{p\\in P\}\\hat\{\\pi\}\_\{t\}\(p\)\\log\_\{2\}\\hat\{\\pi\}\_\{t\}\(p\)\. For plotting, the information efficiency of step tt is IE1​k​\(t\)=1000⋅Δ​Htmax⁡\{τt,1\},Δ​Ht=max⁡\{Ht−Ht\+1,0\},\\mathrm\{IE\}\_\{1\\mathrm\{k\}\}\(t\)=1000\\cdot\\frac\{\\Delta H\_\{t\}\}\{\\max\\\{\\tau\_\{t\},1\\\}\},\\qquad\\Delta H\_\{t\}=\\max\\\{H\_\{t\}\-H\_\{t\+1\},0\\\}, where HtH\_\{t\} is computed before the Beta update and Ht\+1H\_\{t\+1\} is computed after the update\. At each step, the policy chooses one prompt ptp\_\{t\}, performs one model call, then updates \(α,β\)\(\\alpha,\\beta\) and c^\\hat\{c\}\. Under the mutual information rule, the expected next entropy after one more labeled sample on pp is approximated by 𝔼​\[Ht\+1∣p\]≈mp​H​\(P⋆∣αp\+1,βp\)\+\(1−mp\)​H​\(P⋆∣αp,βp\+1\),\\mathbb\{E\}\[H\_\{t\+1\}\\mid p\]\\approx m\_\{p\}\\,H\(P^\{\\star\}\\mid\\alpha\_\{p\}\{\+\}1,\\beta\_\{p\}\)\+\(1\-m\_\{p\}\)\\,H\(P^\{\\star\}\\mid\\alpha\_\{p\},\\beta\_\{p\}\{\+\}1\), where each entropy term is recomputed by the same Monte Carlo procedure after the hypothetical update on pp only\. The acquisition score divides expected entropy reduction by estimated token cost, utMI​\(p\)=max⁡\{Ht−𝔼​\[Ht\+1∣p\],0\}max⁡\{c^p,1\},pt=arg⁡maxp∈P⁡utMI​\(p\)\.u\_\{t\}^\{\\mathrm\{MI\}\}\(p\)=\\frac\{\\max\\\{H\_\{t\}\-\\mathbb\{E\}\[H\_\{t\+1\}\\mid p\],0\\\}\}\{\\max\\\{\\hat\{c\}\_\{p\},1\\\}\},\\qquad p\_\{t\}=\\arg\\max\_\{p\\in P\}u\_\{t\}^\{\\mathrm\{MI\}\}\(p\)\. Under the knowledge gradient rule, let mmax=maxj∈P⁡mjm\_\{\\max\}=\\max\_\{j\\in P\}m\_\{j\} be the current best posterior mean\. If prompt pp were sampled and succeeded, its mean would become \(αp\+1\)/\(αp\+βp\+1\)\(\\alpha\_\{p\}\{\+\}1\)/\(\\alpha\_\{p\}\{\+\}\\beta\_\{p\}\{\+\}1\)\. If it failed, its mean would become αp/\(αp\+βp\+1\)\\alpha\_\{p\}/\(\\alpha\_\{p\}\{\+\}\\beta\_\{p\}\{\+\}1\)\. Let mmaxsucc​\(p\)m\_\{\\max\}^\{\\mathrm\{succ\}\}\(p\) and mmaxfail​\(p\)m\_\{\\max\}^\{\\mathrm\{fail\}\}\(p\) be the resulting best means across prompts under these two hypothetical updates\. Define KGt​\(p\)\\displaystyle\\mathrm\{KG\}\_\{t\}\(p\) =mp​max⁡\{mmaxsucc​\(p\)−mmax,0\}\+\(1−mp\)​max⁡\{mmaxfail​\(p\)−mmax,0\},\\displaystyle=m\_\{p\}\\,\\max\\\{m\_\{\\max\}^\{\\mathrm\{succ\}\}\(p\)\-m\_\{\\max\},0\\\}\+\(1\-m\_\{p\}\)\\,\\max\\\{m\_\{\\max\}^\{\\mathrm\{fail\}\}\(p\)\-m\_\{\\max\},0\\\}, utKG​\(p\)\\displaystyle u\_\{t\}^\{\\mathrm\{KG\}\}\(p\) =KGt​\(p\)max⁡\{c^p,1\},\\displaystyle=\\frac\{\\mathrm\{KG\}\_\{t\}\(p\)\}\{\\max\\\{\\hat\{c\}\_\{p\},1\\\}\}, \(22\) and select pt=arg⁡maxp∈P⁡utKG​\(p\)p\_\{t\}=\\arg\\max\_\{p\\in P\}u\_\{t\}^\{\\mathrm\{KG\}\}\(p\)\. A mixed rule combines the epistemic score utMIu\_\{t\}^\{\\mathrm\{MI\}\} and the pragmatic score utKGu\_\{t\}^\{\\mathrm\{KG\}\}, st​\(p\)=λt​utMI​\(p\)\+\(1−λt\)​utKG​\(p\),pt=arg⁡maxp∈P⁡st​\(p\)\.s\_\{t\}\(p\)=\\lambda\_\{t\}\\,u\_\{t\}^\{\\mathrm\{MI\}\}\(p\)\+\(1\-\\lambda\_\{t\}\)\\,u\_\{t\}^\{\\mathrm\{KG\}\}\(p\),\\qquad p\_\{t\}=\\arg\\max\_\{p\\in P\}s\_\{t\}\(p\)\. In the notebook implementation, this mixed rule is computed as an Expected Free Energy score Gt​\(p\)=−st​\(p\)G\_\{t\}\(p\)=\-s\_\{t\}\(p\) and the selected prompt is pt=arg⁡minp⁡Gt​\(p\)p\_\{t\}=\\arg\\min\_\{p\}G\_\{t\}\(p\), which is equivalent\. The weight decays linearly over the available training steps, λt=max⁡\(0\.1, 1−tT−1\),\\lambda\_\{t\}=\\max\\\!\\left\(0\.1,\\;1\-\\frac\{t\}\{T\-1\}\\right\), where TT is the number of available training steps, at most 400400\. Thompson sampling draws one θ~p∼Beta​\(αp,βp\)\\tilde\{\\theta\}\_\{p\}\\sim\\mathrm\{Beta\}\(\\alpha\_\{p\},\\beta\_\{p\}\) per prompt and chooses pt=arg⁡maxp∈P⁡θ~pp\_\{t\}=\\arg\\max\_\{p\\in P\}\\tilde\{\\theta\}\_\{p\}\. Round robin cycles deterministically through the prompt set with ptp\_\{t\} equal to the tmod\|P\|t\\bmod\|P\| element under a fixed ordering of PP\. After training, the selected prompt is the posterior mean maximizer p^=arg⁡maxp∈P⁡mp\\hat\{p\}=\\arg\\max\_\{p\\in P\}m\_\{p\}\. This single prompt is then evaluated on the shared holdout set using the same user template and the same parsing rule\. Reported holdout accuracy is the fraction of correct parses, and token statistics are computed from the API token usage for those calls\. As a concrete example, suppose pt=units\_and\_scalesp\_\{t\}=\\texttt\{units\\\_and\\\_scales\}, the parsed model reply is B, the gold key is B, and the API reports τt=134\\tau\_\{t\}=134\. Then yt=1y\_\{t\}=1, the posterior for that prompt updates from Beta​\(1,1\)\\mathrm\{Beta\}\(1,1\) to Beta​\(2,1\)\\mathrm\{Beta\}\(2,1\), and its cost estimate updates to c^←0\.9​c^\+0\.1⋅134\\hat\{c\}\\leftarrow 0\.9\\,\\hat\{c\}\+0\.1\\cdot 134\. All acquisition scores for the next step are computed from the updated posteriors and cost estimates\. Appendix F Jailbreaking and Defensive Design Adaptive prompt attacks can be viewed as a learning process\. Each exchange provides feedback, and that feedback can be used to refine later attempts\. The same information accounting used in benign interaction can therefore be turned around and used to describe what an attacker learns about a defense surface\. The aim here is to formalize this structure and to suggest defensive objectives\. It is not to propose new attack methods\. Let x~t\\tilde\{x\}\_\{t\} denote the visible text presented to the model at turn tt\. Let d=\(s,ϕ,κ,πclar,g,f,ρ\)d=\(s,\\phi,\\kappa,\\pi\_\{\\mathrm\{clar\}\},g,f,\\rho\) collect the system prompt ss, guard parameters ϕ\\phi, decoding constraints κ\\kappa, a clarifying policy πclar\\pi\_\{\\mathrm\{clar\}\}, tool and data access rules gg, filters ff, and rate limits ρ\\rho\. Let dpubd\_\{\\mathrm\{pub\}\} denote the components of dd observable to the attacker\. An action ata\_\{t\} represents any intervention that changes what the model sees next, such as editing the prompt or influencing retrieved context\. Given \(x~t,at,d\)\(\\tilde\{x\}\_\{t\},a\_\{t\},d\), the system produces a response YtY\_\{t\} with Yt∼pθ​\(y∣x~t,at,d\)\.Y\_\{t\}\\sim p\_\{\\theta\}\(y\\mid\\tilde\{x\}\_\{t\},a\_\{t\},d\)\. Let 𝒰\\mathcal\{U\} denote a set of undesired outcomes and let Vt=𝟏​\{Yt∈𝒰\}V\_\{t\}=\\mathbf\{1\}\\\{Y\_\{t\}\\in\\mathcal\{U\}\\\} be the associated indicator at turn tt\. In tool using systems, 𝒰\\mathcal\{U\} can be understood broadly\. It can include unsafe text, unauthorized tool actions, or leakage of sensitive data through outputs or tool calls\. Let V=𝟏​\{∃t≤T:Vt=1\}V=\\mathbf\{1\}\\\{\\exists t\\leq T:\\,V\_\{t\}=1\\\} denote the session level failure indicator\. Let ZtZ\_\{t\} denote an observable signal derived from the tt\-th exchange, such as a refusal flag, the returned text, tool call traces, error messages, or coarse timing and length cues\. A stylized adaptive attacker can be modeled with latent variables Ξ\\Xi that represent unknown aspects of the system that are useful for exploitation\. Examples include which instruction sources dominate, which filters fail under stress, or which tool routes expose sensitive resources\. Let ht−1h\_\{t\-1\} denote the interaction history available to the attacker up to turn t−1t\-1\. Starting from a prior q1​\(Ξ\)q\_\{1\}\(\\Xi\), after choosing ata\_\{t\} and observing ZtZ\_\{t\}, the attacker updates a belief by Bayes qt\+1​\(Ξ\)∝qt​\(Ξ\)​p​\(Zt∣Ξ,ht−1,at,dpub\)\.q\_\{t\+1\}\(\\Xi\)\\propto q\_\{t\}\(\\Xi\)\\,p\(Z\_\{t\}\\mid\\Xi,h\_\{t\-1\},a\_\{t\},d\_\{\\mathrm\{pub\}\}\)\. A single step action rule that makes the exploration and exploitation trade explicit is at∈arg⁡maxa∈𝒜⁡\[𝔼​\[Vt∣ht−1,a,qt,dpub\]\+λ​Iqt​\(Ξ;Zt∣ht−1,a,dpub\)\]s\.t\.∑k=1ttokens​\(ak\)≤B\.a\_\{t\}\\in\\arg\\max\_\{a\\in\\mathcal\{A\}\}\\Big\[\\mathbb\{E\}\[V\_\{t\}\\mid h\_\{t\-1\},a,q\_\{t\},d\_\{\\mathrm\{pub\}\}\]\+\\lambda\\,I\_\{q\_\{t\}\}\(\\Xi;Z\_\{t\}\\mid h\_\{t\-1\},a,d\_\{\\mathrm\{pub\}\}\)\\Big\]\\quad\\text\{s\.t\.\}\\quad\\sum\_\{k=1\}^\{t\}\\mathrm\{tokens\}\(a\_\{k\}\)\\leq B\. \(23\) The first term rewards actions that are likely to succeed immediately\. The second rewards actions whose observable consequences reduce uncertainty about Ξ\\Xi, which can make later actions more effective\. A defender chooses dd once and then faces an adaptive policy\. Let α\\alpha denote an attacker policy that maps the interaction history to actions and obeys the same budget\. Let 𝗂𝗇𝗍𝖾𝗇𝗍∈\{benign,adversarial\}\\mathsf\{intent\}\\in\\\{\\mathrm\{benign\},\\mathrm\{adversarial\}\\\} denote the session type\. A robust design objective can be written as mind∈𝒟\\displaystyle\\min\_\{d\\in\\mathcal\{D\}\} supα∈ΠB\[𝔼​\[V∣d,α\]\+λ1​Iq1​\(Ξ;Z1:T∣dpub,α\)\+λ2​cost​\(d\)\]\\displaystyle\\sup\_\{\\alpha\\in\\Pi\_\{B\}\}\\Big\[\\mathbb\{E\}\[V\\mid d,\\alpha\]\+\\lambda\_\{1\}I\_\{q\_\{1\}\}\(\\Xi;Z\_\{1:T\}\\mid d\_\{\\mathrm\{pub\}\},\\alpha\)\+\\lambda\_\{2\}\\mathrm\{cost\}\(d\)\\Big\] \(24\) s\.t\. 𝔼​\[utility∣d,𝗂𝗇𝗍𝖾𝗇𝗍=benign\]≥τ\.\\displaystyle\\mathbb\{E\}\[\\mathrm\{utility\}\\mid d,\\ \\mathsf\{intent\}=\\mathrm\{benign\}\]\\geq\\tau\. where Z1:TZ\_\{1:T\} denotes the sequence of observed signals, ΠB\\Pi\_\{B\} is the set of budget constrained adaptive attacker policies, and the mutual information term is computed under the attacker prior q1q\_\{1\}\. The information term penalizes designs that allow rapid learning about Ξ\\Xi through interaction\. The constraint enforces acceptable utility on benign sessions\. It is often useful to report a token normalized leakage rate\. Define IE1​k=1000​∑t=1TΔ​It∑t=1Ttokens​\(at\),Δ​It=KL​\(qt\+1​\(Ξ\)∥qt​\(Ξ\)\)\.\\mathrm\{IE\}\_\{1\\mathrm\{k\}\}=1000\\,\\frac\{\\sum\_\{t=1\}^\{T\}\\Delta I\_\{t\}\}\{\\sum\_\{t=1\}^\{T\}\\mathrm\{tokens\}\(a\_\{t\}\)\},\\qquad\\Delta I\_\{t\}=\\mathrm\{KL\}\\\!\\big\(q\_\{t\+1\}\(\\Xi\)\\,\\\|\\,q\_\{t\}\(\\Xi\)\\big\)\. Under a Bayesian update, Δ​It\\Delta I\_\{t\} is the realized information gain about Ξ\\Xi from observing ZtZ\_\{t\}\. A bound of the form IE1​k≤η\\mathrm\{IE\}\_\{1\\mathrm\{k\}\}\\leq\\eta limits the total information learned about Ξ\\Xi to scale linearly with the total interaction budget\. Several practical controls map cleanly onto these terms\. Refusal shaping aims to make the refusal branch as uninformative as possible\. Let FtF\_\{t\} denote the refusal indicator at turn tt\. In an idealized model with no other side channels, drawing refusals from a fixed distribution that does not depend on Ξ\\Xi yields I\(Ξ;Yt∣Ft=1,dpub\)=0I\(\\Xi;Y\_\{t\}\\mid F\_\{t\}=1,d\_\{\\mathrm\{pub\}\}\)=0\. In practice, it also helps to control easy cues such as response length, formatting, and latency\. Separation of authority targets indirect prompt injection and related failures where untrusted text is treated as control\. The configuration dd can restrict tool permissions, keep secrets out of the model context, and ensure that untrusted content cannot directly trigger privileged actions\. Deterministic validation of outputs and tool calls, and explicit approval for high risk actions, reduce the value of any single successful manipulation\. Finally, budgets and rate limits directly bound the total interaction length \(with output length capped by κ\\kappa\) and therefore bound total leakage even when per step leakage cannot be driven to zero\. Information terms are difficult to estimate in real systems, and Ξ\\Xi is a modeling choice rather than a directly observable quantity\. In practice, mutual information is approximated using surrogate models, calibrated uncertainty estimates, and Monte Carlo evaluation\. The main point is structural, i\.e\., defense can be framed not only as reducing the chance of an undesired outcome, but also as reducing the rate at which an attacker learns from interaction\. Appendix G The Active Inference View of Bilevel Reinforcement Learning Bilevel reinforcement learning and active inference share a two level structure\. An outer choice fixes the conditions of a control problem, and an inner solution responds by producing behavior that is optimal under those conditions\. In reinforcement learning the inner object is a policy that maximizes expected return in an induced MDP\. In active inference the inner object is an inference step that updates beliefs, and the outer object selects actions that balance preferred outcomes against uncertainty reduction\. In bilevel reinforcement learning, a designer selects configuration variables xx, such as reward weights, prompt parameters, or safety settings\. A context ξ\\xi is drawn from a distribution 𝒟\\mathcal\{D\}, and together \(ξ,x\)\(\\xi,x\) define an MDP M​\(ξ,x\)M\(\\xi,x\) with horizon HH\. The agent computes a best response policy π∗\(⋅∣ξ,x\)∈argmaxπJ\(π;ξ,x\),J\(π;ξ,x\)=𝔼\[∑t=1Hrt\]\.\\pi^\{\*\}\(\\cdot\\mid\\xi,x\)\\in\\arg\\max\_\{\\pi\}J\(\\pi;\\xi,x\),\\qquad J\(\\pi;\\xi,x\)=\\mathbb\{E\}\\\!\\Big\[\\sum\_\{t=1\}^\{H\}r\_\{t\}\\Big\]\. The outer problem chooses xx to optimize expected performance under this response, often with a regularizer Ω\\Omega, minx−𝔼ξ∼𝒟​\[J​\(π∗;ξ,x\)\]\+Ω​\(x\)\.\\min\_\{x\}\\ \-\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{D\}\}\\\!\\big\[J\(\\pi^\{\*\};\\xi,x\)\\big\]\+\\Omega\(x\)\. This captures contextual Stackelberg style design problems, where a leader selects xx and a follower solves the induced MDP, and it also covers outer loop design in modern learning systems \(Thoma et al\., 2024; Shen et al\., 2024\)\. Active inference evaluates behavior through expected free energy\. Preferences are encoded by a distribution p⋆​\(ot\)p^\{\\star\}\(o\_\{t\}\) over observations, and latent variables Θ\\Theta represent what remains uncertain and worth inferring\. A horizon objective that matches the standard risk and epistemic decomposition can be written as 𝒢H​\(π;x\)=𝔼​\[∑t=1H−ln⁡p⋆​\(ot\)\+𝒜t−λ​I​\(Θ;ot∣ht−1,π,x\)\],\\mathcal\{G\}\_\{H\}\(\\pi;x\)=\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{H\}\-\\ln p^\{\\star\}\(o\_\{t\}\)\+\\mathcal\{A\}\_\{t\}\-\\lambda\\,I\(\\Theta;o\_\{t\}\\mid h\_\{t\-1\},\\pi,x\)\\right\], where ht−1h\_\{t\-1\} denotes the history up to time t−1t\-1, and 𝒜t\\mathcal\{A\}\_\{t\} is an ambiguity term that penalizes observations that remain noisy even when Θ\\Theta is known\. All expectations, entropies, and mutual informations are taken under the predictive distribution induced by the generative model and the policy π\\pi, conditional on ht−1h\_\{t\-1\} and xx\. A convenient choice is 𝒜t=𝔼​\[H​\(ot∣Θ,ht−1,π,x\)\]\.\\mathcal\{A\}\_\{t\}=\\mathbb\{E\}\\\!\\left\[H\\\!\\left\(o\_\{t\}\\mid\\Theta,h\_\{t\-1\},\\pi,x\\right\)\\right\]\. When the observation model is deterministic given Θ\\Theta and the chosen action, 𝒜t\\mathcal\{A\}\_\{t\} vanishes and the epistemic term reduces to expected information gain\. In that deterministic case, minimizing expected free energy reduces to minimizing expected risk while maximizing information gain \(Friston et al\., 2017; Parr and Friston, 2019\)\. The link to reward maximization becomes explicit once preferences are written as reward\. Define rtpref=ln⁡p⋆​\(ot\)\.r\_\{t\}^\{\\mathrm\{pref\}\}=\\ln p^\{\\star\}\(o\_\{t\}\)\. Maximizing ∑trtpref\\sum\_\{t\}r\_\{t\}^\{\\mathrm\{pref\}\} is equivalent to minimizing the cumulative risk term ∑t−ln⁡p⋆​\(ot\)\\sum\_\{t\}\-\\ln p^\{\\star\}\(o\_\{t\}\)\. If an intrinsic term is added that rewards information gain, then a return objective aligns with the expected free energy form\. One simple epistemic reward is rtepi=λ​I​\(Θ;ot∣ht−1,π,x\),r\_\{t\}^\{\\mathrm\{epi\}\}=\\lambda\\,I\(\\Theta;o\_\{t\}\\mid h\_\{t\-1\},\\pi,x\), together with a penalty that matches ambiguity\. The combined return r~t=rtpref\+rtepi−𝒜t\\tilde\{r\}\_\{t\}=r\_\{t\}^\{\\mathrm\{pref\}\}\+r\_\{t\}^\{\\mathrm\{epi\}\}\-\\mathcal\{A\}\_\{t\} mirrors the expected free energy objective up to constants and sign conventions\. The alignment is at the level of objectives\. The modeling stance still differs, since active inference represents goals as preferences over observations and treats belief dynamics as part of the state, while reinforcement learning often treats rewards as primitive and leaves inference implicit\. When information acquisition has an operational cost, the outer design problem can trade off task value, cost, and information\. It is often useful to separate information that supports performance from information that should be difficult to extract\. Let ct​\(x\)c\_\{t\}\(x\) denote operational cost, such as token usage or tool latency\. Let Θtask\\Theta\_\{\\mathrm\{task\}\} denote variables whose rapid identification is beneficial, and let Θsens\\Theta\_\{\\mathrm\{sens\}\} denote variables whose rapid identification is undesirable\. Define ℐtask​\(x\)=𝔼​\[∑t=1HI​\(Θtask;ot∣ht−1,π∗,x\)\],ℐsens​\(x\)=𝔼​\[∑t=1HI​\(Θsens;ot∣ht−1,π∗,x\)\]\.\\mathcal\{I\}\_\{\\mathrm\{task\}\}\(x\)=\\mathbb\{E\}\\\!\\Big\[\\sum\_\{t=1\}^\{H\}I\(\\Theta\_\{\\mathrm\{task\}\};o\_\{t\}\\mid h\_\{t\-1\},\\pi^\{\*\},x\)\\Big\],\\quad\\mathcal\{I\}\_\{\\mathrm\{sens\}\}\(x\)=\\mathbb\{E\}\\\!\\Big\[\\sum\_\{t=1\}^\{H\}I\(\\Theta\_\{\\mathrm\{sens\}\};o\_\{t\}\\mid h\_\{t\-1\},\\pi^\{\*\},x\)\\Big\]\. One possible outer objective is minx−𝔼ξ​\[J​\(π∗;ξ,x\)\]\+μ​𝔼​\[∑t=1Hct​\(x\)\]−γ​ℐtask​\(x\)\+η​ℐsens​\(x\),\\min\_\{x\}\\ \-\\mathbb\{E\}\_\{\\xi\}\\\!\\big\[J\(\\pi^\{\*\};\\xi,x\)\\big\]\+\\mu\\,\\mathbb\{E\}\\\!\\Big\[\\sum\_\{t=1\}^\{H\}c\_\{t\}\(x\)\\Big\]\-\\gamma\\,\\mathcal\{I\}\_\{\\mathrm\{task\}\}\(x\)\+\\eta\\,\\mathcal\{I\}\_\{\\mathrm\{sens\}\}\(x\), with γ,η,μ≥0\\gamma,\\eta,\\mu\\geq 0\. The same bilevel machinery applies, since π∗\\pi^\{\*\} is still the inner best response, and the outer variables can be updated using hypergradients that differentiate through this inner solution, as in BLPO \(Prakash et al\., 2025\)\. For language model agents, clarifying questions and tool calls are actions that purchase information at a measurable token cost\. The preceding objectives make the trade between utility, cost, and uncertainty reduction explicit\. Increasing the weight on task relevant information gain encourages earlier probing, and increasing the weight on sensitive information discourages probing that may overreach, while keeping the inner and outer roles of inference and control distinct\.`