Ask the World Before Acting: Budgeted Environment Probing for World-Model Calibration

# Budgeted Environment Probing for World-Model Calibration
Source: [https://arxiv.org/html/2606.31422](https://arxiv.org/html/2606.31422)
## Ask the World Before Acting: Budgeted Environment Probing for World\-Model Calibration

Xinyuan Song1Zekun Cai2,3 1Emory University, Atlanta, GA, USA2The University of Tokyo, Tokyo, Japan 3LocationMind, Tokyo, Japan xinyuan\.song@emory\.edu, caizekun@csis\.u\-tokyo\.ac\.jp

###### Abstract

Long\-horizon language agents do not only choose actions; they carry a private model of the world from one decision to the next\. When that model drifts, a later failure can be decided before the failing action is ever taken\. We study a direct repair mechanism: before committing to the next task action, an agent may ask the environment about one belief field and write the answer back into its world model\. This makes environment interaction a scarce calibration resource, not merely a way to advance the task\. We introduce EnvProbe, a budgeted probing operator for structured belief tables\. The useful probes are not the same everywhere\. Procedural beliefs, such as tool dependencies, can often be repaired by targeted checks, but those checks spend steps that the task may need\. Spatial beliefs, such as object locations and graph edges, rely more on structural cues; the agent’s own confidence can be a poor guide when the world changes off\-screen\. A type\-stratified analysis formalizes this probe\-action frontier, and controlled experiments show that mid\-planning environment evidence reduces terminal world\-model error when the probe policy follows the structure of the task\. Code and environments are available at[github\.com/Hik289/Environment\-reduce\-error](https://github.com/Hik289/Environment-reduce-error.git)\.

Ask the World Before Acting: Budgeted Environment Probing for World\-Model Calibration

Xinyuan Song1Zekun Cai2,31Emory University, Atlanta, GA, USA2The University of Tokyo, Tokyo, Japan3LocationMind, Tokyo, Japanxinyuan\.song@emory\.edu, caizekun@csis\.u\-tokyo\.ac\.jp

## 1Introduction

Language agents increasingly work by carrying state\. They remember which tool has been initialized, where an object was last seen, which precondition is satisfied, and which edge in a graph is traversable\. This running model is implicit in reasoning\-and\-acting agents such as ReAct, Reflexion, and LATS\(Yaoet al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib6); Shinnet al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib7); Zhouet al\.,[2024a](https://arxiv.org/html/2606.31422#bib.bib11)\), explicit in many tool\-use and embodied systems\(Schicket al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib12); Qinet al\.,[2024](https://arxiv.org/html/2606.31422#bib.bib13); Huanget al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib8); Ahnet al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib9)\), and central to recent web and long\-horizon benchmarks\(Shridharet al\.,[2021](https://arxiv.org/html/2606.31422#bib.bib15); Wanget al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib25); Zhouet al\.,[2024b](https://arxiv.org/html/2606.31422#bib.bib16); Denget al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib17); Luoet al\.,[2025](https://arxiv.org/html/2606.31422#bib.bib24)\)\. The loop is simple: reason over the model, act, observe, and continue\. It is also fragile, because the reasoning step quietly assumes that the model is still close enough to the environment\.

Long horizons make this assumption fragile\. The model can drift even when every local generation looks plausible: a tool believed to be loaded may have become unavailable; a key believed to be in a room may have moved; a route that looked open may now be blocked\. Once the agent plans on top of the stale premise, the eventual error looks like a bad final action, even though the failure began earlier in the belief state\(Wanget al\.,[2026](https://arxiv.org/html/2606.31422#bib.bib23); Luoet al\.,[2025](https://arxiv.org/html/2606.31422#bib.bib24)\)\. This is a different failure mode from insufficient chain\-of\-thought or weak tool selection\. The agent may have the right high\-level plan but the wrong world on which to execute it\.

The environment itself contains the missing evidence\. The agent can ask whether a particular field is still true, just as a software system can query an API, a robot can look at a drawer again, or a web agent can re\-open a page before executing a dependent step\. The question is not whether more information is useful in the abstract\. Each check consumes the same limited horizon as task\-advancing actions\. An agent that probes too little acts confidently on stale beliefs; an agent that probes too much spends the episode verifying the world instead of changing it\. The same tension appears in classical partially observable planning and value\-of\-information methods\(Kaelblinget al\.,[1998](https://arxiv.org/html/2606.31422#bib.bib35); Rosset al\.,[2008](https://arxiv.org/html/2606.31422#bib.bib36); Chaloner and Verdinelli,[1995](https://arxiv.org/html/2606.31422#bib.bib37); Golovin and Krause,[2011](https://arxiv.org/html/2606.31422#bib.bib38)\), but language\-agent world models add a new wrinkle: the belief state is a symbolic table written by a model, and the available probe signals include noisy self\-reports such as confidence and recency\. Prior work shows that such confidence can be useful yet miscalibrated\(Guoet al\.,[2017](https://arxiv.org/html/2606.31422#bib.bib39); Kadavathet al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib40)\); our question is when it should control an environment query\.

We introduce EnvProbe, a probing operator for language agents with explicit structured belief tables\. At each planning step, EnvProbe scores candidate fields using task structure, belief recency, verbalized confidence, and dependency role\. The chosen probe returns the current environment value for that field and updates the world model before the next plan is formed\. Unlike retrieval augmentation, reflection, or asking the user for missing information\(Shinnet al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib7); Huet al\.,[2024](https://arxiv.org/html/2606.31422#bib.bib1); Fang and Ke,[2025](https://arxiv.org/html/2606.31422#bib.bib2); Dongreet al\.,[2024](https://arxiv.org/html/2606.31422#bib.bib5)\), EnvProbe treats the environment itself as the evidence source and asks which already\-populated belief should be verified now\.

The experiments separate two regimes\. Procedural beliefs, such as tool preconditions and subgoal dependencies, benefit from targeted checks because the action trace gives clues about what may have gone stale\. The same checks, however, compete with the dependency chain for scarce action slots\. Spatial beliefs, such as object locations and graph edges, behave differently: structural task cues remain useful, while the agent’s own uncertainty report can mislead when exogenous changes leave little trace in the history\.

Our contributions are:

- •a budgeted environment\-probing operator for structured world models in language agents;
- •a type\-stratified mathematical account that separates belief repair from task\-action displacement;
- •controlled environments and probe\-aware metrics that expose world\-model error before task success collapses; and
- •empirical evidence that structural probe scores reduce terminal belief error, while self\-reported uncertainty must be treated as a noisy signal rather than a reliable oracle\.

![Refer to caption](https://arxiv.org/html/2606.31422v1/x1.png)Figure 1:Probe\-action budget trade\-off\.Long\-horizon agents can use the environment during planning to repair stale world\-model fields\. The benefit depends on belief type: procedural fields are easier to target but more exposed to action displacement, while spatial fields often favor structural probes over self\-reported uncertainty\.
## 2Related Work

##### LLM agents with implicit or explicit state\.

ReAct, Reflexion, Toolformer, ToolLLM, and LATS establish the now\-standard pattern of interleaving language reasoning with environment or tool actions\(Yaoet al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib6); Shinnet al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib7); Schicket al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib12); Qinet al\.,[2024](https://arxiv.org/html/2606.31422#bib.bib13); Zhouet al\.,[2024a](https://arxiv.org/html/2606.31422#bib.bib11)\)\. Embodied and web\-agent systems further ground language plans in affordances or interactive interfaces\(Huanget al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib8); Ahnet al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib9); Wanget al\.,[2024](https://arxiv.org/html/2606.31422#bib.bib20); Zhouet al\.,[2024b](https://arxiv.org/html/2606.31422#bib.bib16)\)\. These systems update state through observations, execution traces, reflection, or memory, but they do not isolate*probing*as a budgeted action whose purpose is only to repair a structured belief table\. Recent work on memory\-environment realignment and rule\-augmented memory recognizes related drift phenomena\(Yin and Du,[2026](https://arxiv.org/html/2606.31422#bib.bib3); Yuanet al\.,[2026](https://arxiv.org/html/2606.31422#bib.bib4)\), while EnvProbe studies the selection problem: which field should be checked when only a few checks are affordable?

##### Information gathering under partial observability\.

Classical POMDPs provide a formal account of belief\-state planning under partial observability\(Kaelblinget al\.,[1998](https://arxiv.org/html/2606.31422#bib.bib35); Rosset al\.,[2008](https://arxiv.org/html/2606.31422#bib.bib36)\)\. Bayesian experimental design and adaptive submodularity formalize the value of information and greedy selection under uncertainty\(Chaloner and Verdinelli,[1995](https://arxiv.org/html/2606.31422#bib.bib37); Golovin and Krause,[2011](https://arxiv.org/html/2606.31422#bib.bib38); Krause and Golovin,[2014](https://arxiv.org/html/2606.31422#bib.bib41)\)\. EnvProbe inherits the same information\-action tension, but differs in two ways: the belief state is a collection of symbolic fields maintained by an LLM, and the selector uses noisy self\-reports such as staleness and confidence\. This makes the surrogate\-quality question empirical as well as mathematical\.

##### LLM uncertainty and confidence calibration\.

Modern neural predictors are often miscalibrated\(Guoet al\.,[2017](https://arxiv.org/html/2606.31422#bib.bib39)\), and language models can sometimes estimate answer validity while still failing under distribution shift or open\-ended generation\(Kadavathet al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib40)\)\. UoT uses model\-estimated uncertainty to ask informative questions\(Huet al\.,[2024](https://arxiv.org/html/2606.31422#bib.bib1)\); InfoSeeker plans information gathering under partial observability\(Fang and Ke,[2025](https://arxiv.org/html/2606.31422#bib.bib2)\); ReSpAct adds speaking actions for clarification\(Dongreet al\.,[2024](https://arxiv.org/html/2606.31422#bib.bib5)\)\. Our setting is different: the agent is not asking a user for missing facts, but deciding whether to spend scarce environment actions to verify an already populated belief field\. The confident\-wrong rate measured in our environments motivates a formal miscoverage bound for uncertainty\-only probing \(Proposition[5\.5](https://arxiv.org/html/2606.31422#S5.Thmtheorem5)\)\.

##### Agent benchmarks and evaluation metrics\.

Benchmarks such as ALFWorld, WebArena, VisualWebArena, Mind2Web, AgentBench, and UltraHorizon evaluate long\-horizon or interactive agents\(Shridharet al\.,[2021](https://arxiv.org/html/2606.31422#bib.bib15); Zhouet al\.,[2024b](https://arxiv.org/html/2606.31422#bib.bib16); Kohet al\.,[2024](https://arxiv.org/html/2606.31422#bib.bib18); Denget al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib17); Liuet al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib19); Luoet al\.,[2025](https://arxiv.org/html/2606.31422#bib.bib24)\)\. They primarily report task completion, which is the right end metric but makes it difficult to diagnose whether a failure came from stale beliefs, invalid plans, or execution\. Our environments expose gold field states so that world\-state accuracy, useful\-probe rate, and collapse onset can be measured alongside task success\.

##### Positioning\.

EnvProbe connects these threads by treating environment checks as first\-class, budgeted actions in LLM agents\. The paper’s contribution is not a new POMDP solver; it is an empirical and theoretical characterization of when LLM\-derived probe scores are reliable, when they are misleading, and how this reliability changes across belief types\.

## 3Problem Setup

We consider a long\-horizon language agent that maintains an explicit*belief world model*\. The model is a structured table rather than a raw conversation transcript: each field records a fact that can be queried, used by the planner, and compared with environment truth\.

##### Belief fields and accuracy\.

Letℱ=\{1,…,n\}\\mathcal\{F\}=\\\{1,\\ldots,n\\\}be the set of belief fields\. Fieldiitakes values in𝒱i\\mathcal\{V\}\_\{i\}\. At stept∈\{0,…,H\}t\\in\\\{0,\\ldots,H\\\}, the environment has gold valuegti∈𝒱ig\_\{t\}^\{i\}\\in\\mathcal\{V\}\_\{i\}, while the agent stores beliefbti∈𝒱ib\_\{t\}^\{i\}\\in\\mathcal\{V\}\_\{i\}\. The terminal world\-state accuracy is

AH=1n​∑i=1n𝟏​\{bHi=gHi\}\.A\_\{H\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{b\_\{H\}^\{i\}=g\_\{H\}^\{i\}\\\}\.\(1\)Task success is a separate event: an agent may have a more accurate world model yet still fail if it spends too many actions checking the world\.

###### Definition 3\.1\(Probe API\)\.

At steptt,Probe​\(i\)\\textsc\{Probe\}\(i\)returns the current gold valuegtig\_\{t\}^\{i\}and updatesbt\+1i←gtib\_\{t\+1\}^\{i\}\\leftarrow g\_\{t\}^\{i\}\. A probe consumes one environment step and does not execute a task action\. Each episode has horizonHHand probe budgetB=⌊H/4⌋B=\\lfloor H/4\\rfloor\.

###### Definition 3\.2\(Belief\-type taxonomy\)\.

We partition fields into procedural and spatial types,ℱ=ℱproc⊔ℱspat\\mathcal\{F\}=\\mathcal\{F\}\_\{\\mathrm\{proc\}\}\\sqcup\\mathcal\{F\}\_\{\\mathrm\{spat\}\}\. Procedural fields encode action\-dependent state such as tool dependencies, subgoal completion, and inventory\. Spatial fields encode exogenous state such as object locations, door states, and graph edges\. The distinction matters because an action trace is informative about procedural mutations but only weakly informative about exogenous spatial mutations\.

##### Probe policies\.

A policy chooses at each step either a task action or a probe\. We compareNo\-Probe,Random\-Probe,Periodic\-Probe,Self\-Uncertainty,EnvProbe\-Simple,EnvProbe\-Judge, andOracle\-Probe\. Random and periodic policies are non\-adaptive sensing baselines; Self\-Uncertainty follows the uncertainty\-sampling intuition from active learning\(Lewis and Gale,[1994](https://arxiv.org/html/2606.31422#bib.bib26); Settles,[2009](https://arxiv.org/html/2606.31422#bib.bib27)\)and the confidence calibration literature\(Guoet al\.,[2017](https://arxiv.org/html/2606.31422#bib.bib39); Kadavathet al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib40)\)\. Oracle\-Probe uses gold mismatches and is reported only as an upper\-bound diagnostic\.

![Refer to caption](https://arxiv.org/html/2606.31422v1/x2.png)Figure 2:EnvProbe pipeline\.The agent maintains a structured belief table while the environment evolves\. Before executing the next task action, EnvProbe scores candidate fields, probes a high\-value field when the score and budget permit, and writes the returned environment value back into the world model\. The same horizon pays for both probing and acting, producing the belief\-accuracy/task\-success frontier analyzed in Section[5](https://arxiv.org/html/2606.31422#S5)\.

## 4EnvProbe: Environment Evidence During Planning

### 4\.1Scoring Belief Fields

EnvProbe assigns each field a probe score

ρi​\(t\)=ci\+si​\(t\)\+ui​\(t\)\+di​\(t\),\\rho\_\{i\}\(t\)=c\_\{i\}\+s\_\{i\}\(t\)\+u\_\{i\}\(t\)\+d\_\{i\}\(t\),\(2\)where all components are normalized to\[0,1\]\[0,1\]:

- •ci=wi/maxj⁡wjc\_\{i\}=w\_\{i\}/\\max\_\{j\}w\_\{j\}iscriticality, derived from task\-importance weightswiw\_\{i\}\.
- •si​\(t\)=min⁡\(1,τ^i​\(t\)/10\)s\_\{i\}\(t\)=\\min\(1,\\hat\{\\tau\}\_\{i\}\(t\)/10\)isreported staleness, whereτ^i​\(t\)\\hat\{\\tau\}\_\{i\}\(t\)is the agent’s estimate of how long the field has gone unchecked\.
- •ui​\(t\)=1−confi​\(t\)u\_\{i\}\(t\)=1\-\\mathrm\{conf\}\_\{i\}\(t\)isverbalized uncertainty\.
- •di​\(t\)∈\{0,0\.5,1\}d\_\{i\}\(t\)\\in\\\{0,0\.5,1\\\}is thedependency role: direct blocker, transitive dependency, or unrelated to the next planned action\.

The score has a useful decomposition:

ρi​\(t\)=ci\+di​\(t\)⏟ρistr​\(t\)\+si​\(t\)\+ui​\(t\)⏟ρiself​\(t\)\.\\rho\_\{i\}\(t\)=\\underbrace\{c\_\{i\}\+d\_\{i\}\(t\)\}\_\{\\rho\_\{i\}^\{\\mathrm\{str\}\}\(t\)\}\+\\underbrace\{s\_\{i\}\(t\)\+u\_\{i\}\(t\)\}\_\{\\rho\_\{i\}^\{\\mathrm\{self\}\}\(t\)\}\.\(3\)The structural part comes from the task graph and proposed action\. The self\-report part comes from the model’s own memory and confidence\. Our experiments show that this distinction is not cosmetic: structural signals are stable across belief types, while self\-reports can become anti\-signals when the model is confidently wrong\.

### 4\.2Algorithms

Algorithm 1EnvProbe\-Simple0:Belief table

𝐛0=𝐠0\\mathbf\{b\}\_\{0\}=\\mathbf\{g\}\_\{0\}, task graph

GG, horizon

HH, budget

B=⌊H/4⌋B=\\lfloor H/4\\rfloor
1:

probes\_used←0\\text\{probes\\\_used\}\\leftarrow 0;

t←0t\\leftarrow 0
2:while

t≤Ht\\leq Hdo

3:// Score all belief fields

4:foreach field

i∈ℱi\\in\\mathcal\{F\}do

5:Compute

cic\_\{i\}from task\-weight table

ww
6:

si←min⁡\(1,τ^i​\(t\)/10\)s\_\{i\}\\leftarrow\\min\(1,\\;\\hat\{\\tau\}\_\{i\}\(t\)/10\)\(LLM\-reported staleness\)

7:

ui←1−confi​\(t\)u\_\{i\}\\leftarrow 1\-\\mathrm\{conf\}\_\{i\}\(t\)\(LLM\-reported confidence\)

8:

di←dep\_role​\(i,next\_action​\(t\),G\)d\_\{i\}\\leftarrow\\text\{dep\\\_role\}\(i,\\text\{next\\\_action\}\(t\),G\)
9:

ρi​\(t\)←ci\+si\+ui\+di\\rho\_\{i\}\(t\)\\leftarrow c\_\{i\}\+s\_\{i\}\+u\_\{i\}\+d\_\{i\}
10:endfor

11:if

ρ⋆​\(t\)≜maxi⁡ρi​\(t\)≥1\.5\\rho\_\{\\star\}\(t\)\\triangleq\\max\_\{i\}\\rho\_\{i\}\(t\)\\geq 1\.5and

probes\_used<B\\text\{probes\\\_used\}<Bthen

12:

i⋆←arg⁡maxi⁡ρi​\(t\)i^\{\\star\}\\leftarrow\\arg\\max\_\{i\}\\rho\_\{i\}\(t\)
13:ExecuteProbe\(i⋆\)\(i^\{\\star\}\): set

bt\+1i⋆←gti⋆b\_\{t\+1\}^\{i^\{\\star\}\}\\leftarrow g\_\{t\}^\{i^\{\\star\}\}
14:

probes\_used\+=1\\text\{probes\\\_used\}\\mathrel\{\+\}=1;

τ^i⋆←0\\hat\{\\tau\}\_\{i^\{\\star\}\}\\leftarrow 0
15:else

16:Execute task action

ata\_\{t\}\(advance task\)

17:endif

18:

t←t\+1t\\leftarrow t\+1
19:endwhile

##### EnvProbe\-Simple\.

Algorithm[1](https://arxiv.org/html/2606.31422#alg1)is a greedy threshold policy\. It probes the highest\-scoring field whenmaxi⁡ρi​\(t\)≥1\.5\\max\_\{i\}\\rho\_\{i\}\(t\)\\geq 1\.5and budget remains; otherwise it executes the next task action\.

##### EnvProbe\-Judge\.

The judge variant gives a secondary model the belief table and top scored candidates, then asks for a binary override\. This tests whether a contextual language\-model critic adds signal beyond the explicit score, as in reflection and agent\-critique systems\(Shinnet al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib7); Zhouet al\.,[2024a](https://arxiv.org/html/2606.31422#bib.bib11)\)\.

##### Structural variant and oracles\.

EnvProbe\-\(c\+d\)\(c\{\+\}d\)keeps onlyρi\(c\+d\)=ci\+di​\(t\)\\rho\_\{i\}^\{\(c\+d\)\}=c\_\{i\}\+d\_\{i\}\(t\)and removes the self\-report terms\.Oracle\-Probeprobes a known mismatched field and is not deployable\.Oracle\-TWprobesarg⁡maxi⁡wi​𝟏​\{bti≠gti\}\\arg\\max\_\{i\}w\_\{i\}\\mathbf\{1\}\\\{b\_\{t\}^\{i\}\\neq g\_\{t\}^\{i\}\\\}, aligning the oracle with task\-weighted field importance\.

## 5A Type\-Stratified Probe\-Action Theory

The theory isolates two quantities that are easy to conflate in an agent trace: how much a probe repairs the belief table, and how much the probe displaces task actions\. We write the results for a fixed trajectory prefix and then evaluate the same quantities empirically under paired seeds\.

### 5\.1Belief\-Side Gain

For typeT∈\{proc,spat\}T\\in\\\{\\mathrm\{proc\},\\mathrm\{spat\}\\\}, letℱT⊆ℱ\\mathcal\{F\}\_\{T\}\\subseteq\\mathcal\{F\}be the corresponding field set andnT=\|ℱT\|n\_\{T\}=\|\\mathcal\{F\}\_\{T\}\|\. The type\-specific terminal accuracy is

AHT=1nT​∑i∈ℱT𝟏​\{bHi=gHi\}\.A\_\{H\}^\{T\}=\\frac\{1\}\{n\_\{T\}\}\\sum\_\{i\\in\\mathcal\{F\}\_\{T\}\}\\mathbf\{1\}\\\{b\_\{H\}^\{i\}=g\_\{H\}^\{i\}\\\}\.\(4\)For a setS⊆ℱTS\\subseteq\\mathcal\{F\}\_\{T\}probed before the agent continues, define

GT​\(S\)\\displaystyle G\_\{T\}\(S\)=𝔼​\[AHT∣Probe​\(S\)\]\\displaystyle=\\mathbb\{E\}\\\!\\left\[A\_\{H\}^\{T\}\\mid\\textsc\{Probe\}\(S\)\\right\]\(5\)−𝔼​\[AHT∣Probe​\(∅\)\]\.\\displaystyle\\quad\-\\mathbb\{E\}\\\!\\left\[A\_\{H\}^\{T\}\\mid\\textsc\{Probe\}\(\\emptyset\)\\right\]\.ThusGTG\_\{T\}measures belief repair, not task completion\.

###### Assumption 5\.1\(Diminishing belief repair\)\.

For eachTT, the set functionGT:2ℱT→ℝ≥0G\_\{T\}:2^\{\\mathcal\{F\}\_\{T\}\}\\to\\mathbb\{R\}\_\{\\geq 0\}is monotone and submodular:

GT​\(S\)\\displaystyle G\_\{T\}\(S\)≤GT​\(R\)\\displaystyle\\leq G\_\{T\}\(R\)∀S⊆R⊆ℱT,\\displaystyle\\forall S\\subseteq R\\subseteq\\mathcal\{F\}\_\{T\},\(6\)ΔT​\(i∣S\)\\displaystyle\\Delta\_\{T\}\(i\\mid S\)≥ΔT​\(i∣R\)\\displaystyle\\geq\\Delta\_\{T\}\(i\\mid R\)∀S⊆R,i∉R,\\displaystyle\\forall S\\subseteq R,\\ i\\notin R,\(7\)where

ΔT​\(i∣S\)=GT​\(S∪\{i\}\)−GT​\(S\)\.\\Delta\_\{T\}\(i\\mid S\)=G\_\{T\}\(S\\cup\\\{i\\\}\)\-G\_\{T\}\(S\)\.\(8\)This is the standard diminishing\-return condition used in submodular sensing and adaptive information gathering\(Nemhauseret al\.,[1978](https://arxiv.org/html/2606.31422#bib.bib30); Golovin and Krause,[2011](https://arxiv.org/html/2606.31422#bib.bib38); Krause and Golovin,[2014](https://arxiv.org/html/2606.31422#bib.bib41)\)\.

###### Definition 5\.2\(Marginal selection quality\)\.

A scoreρ\\rhohas type\-TTmarginal qualityγT​\(ρ\)∈\[0,1\]\\gamma\_\{T\}\(\\rho\)\\in\[0,1\]if the fieldiρ​\(S\)i\_\{\\rho\}\(S\)selected at a greedy step satisfies

𝔼​\[ΔT​\(iρ​\(S\)∣S\)\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\Delta\_\{T\}\(i\_\{\\rho\}\(S\)\\mid S\)\\right\]≥γT​\(ρ\)​maxj∈ℱT∖S⁡ΔT​\(j∣S\),\\displaystyle\\geq\\gamma\_\{T\}\(\\rho\)\\max\_\{j\\in\\mathcal\{F\}\_\{T\}\\setminus S\}\\Delta\_\{T\}\(j\\mid S\),\(9\)∀S⊆ℱT\.\\displaystyle\\hskip 27\.0pt\\forall S\\subseteq\\mathcal\{F\}\_\{T\}\.Oracle selection hasγT=1\\gamma\_\{T\}=1\. Random and periodic policies can have smallγT\\gamma\_\{T\}when the useful fields are rare\.

###### Lemma 5\.3\(Targeted belief\-repair bound\)\.

Under Assumption[5\.1](https://arxiv.org/html/2606.31422#S5.Thmtheorem1), let a greedy policy allocateBTB\_\{T\}probes to typeTTand satisfy Eq\. \([9](https://arxiv.org/html/2606.31422#S5.E9)\)\. IfSρ,TS\_\{\\rho,T\}is the set it probes andST⋆​\(BT\)∈arg⁡max\|S\|≤BT⁡GT​\(S\)S\_\{T\}^\{\\star\}\(B\_\{T\}\)\\in\\arg\\max\_\{\|S\|\\leq B\_\{T\}\}G\_\{T\}\(S\), then

𝔼​\[GT​\(Sρ,T\)\]≥\(1−e−γT​\(ρ\)\)​GT​\(ST⋆​\(BT\)\)\.\\mathbb\{E\}\[G\_\{T\}\(S\_\{\\rho,T\}\)\]\\geq\\left\(1\-e^\{\-\\gamma\_\{T\}\(\\rho\)\}\\right\)G\_\{T\}\(S\_\{T\}^\{\\star\}\(B\_\{T\}\)\)\.\(10\)

##### Interpretation\.

Eq\. \([10](https://arxiv.org/html/2606.31422#S5.E10)\) says that probing helps only through the quality of the field selector\. A probe spent on a low\-gain field still pays the same action cost\. Proof in Appendix Section[A\.1](https://arxiv.org/html/2606.31422#A1.SS1)\.

##### Empirical surrogate quality\.

We estimateγT​\(ρ\)\\gamma\_\{T\}\(\\rho\)indirectly by comparing realized gain with a task\-weighted oracle under matched seeds\. This is why the experiments report both the full score and the structural\(c\+d\)\(c\+d\)score: the two scores can have different effectiveγT\\gamma\_\{T\}even under the same probe budget\.

###### Lemma 5\.4\(Self\-report perturbation by belief type\)\.

Lethi​\(t\)=\(ci,di​\(t\)\)h\_\{i\}\(t\)=\(c\_\{i\},d\_\{i\}\(t\)\)be the structural features andzi​\(t\)=\(si​\(t\),ui​\(t\)\)z\_\{i\}\(t\)=\(s\_\{i\}\(t\),u\_\{i\}\(t\)\)the self\-report features\. For a spatial field, define

mi​\(h,z\)\\displaystyle m\_\{i\}\(h,z\)=𝔼​\[Δi​\(t\)∣hi​\(t\)=h,zi​\(t\)=z\],\\displaystyle=\\mathbb\{E\}\[\\Delta\_\{i\}\(t\)\\mid h\_\{i\}\(t\)=h,z\_\{i\}\(t\)=z\],\(11\)mi0​\(h\)\\displaystyle m\_\{i\}^\{0\}\(h\)=𝔼​\[Δi​\(t\)∣hi​\(t\)=h\]\.\\displaystyle=\\mathbb\{E\}\[\\Delta\_\{i\}\(t\)\\mid h\_\{i\}\(t\)=h\]\.\(12\)If

\|mi​\(hi​\(t\),zi​\(t\)\)−mi0​\(hi​\(t\)\)\|≤εspat∀i,t,\\left\|m\_\{i\}\(h\_\{i\}\(t\),z\_\{i\}\(t\)\)\-m\_\{i\}^\{0\}\(h\_\{i\}\(t\)\)\\right\|\\leq\\varepsilon\_\{\\mathrm\{spat\}\}\\quad\\forall i,t,\(13\)then

supϕ​\(h,z\)𝔼​\[Δϕ​\(h,z\)​\(t\)\]−supψ​\(h\)𝔼​\[Δψ​\(h\)​\(t\)\]≤2​εspat\.\\sup\_\{\\phi\(h,z\)\}\\mathbb\{E\}\[\\Delta\_\{\\phi\(h,z\)\}\(t\)\]\-\\sup\_\{\\psi\(h\)\}\\mathbb\{E\}\[\\Delta\_\{\\psi\(h\)\}\(t\)\]\\leq 2\\varepsilon\_\{\\mathrm\{spat\}\}\.\(14\)

##### Interpretation\.

Self\-reports can improve spatial probing only if they carry conditional information about true correction gain beyond task structure\. When exogenous spatial mutations leave little trace in the agent history, Eq\. \([14](https://arxiv.org/html/2606.31422#S5.E14)\) predicts the small gains observed for the full score\. Proof in Appendix Section[A\.2](https://arxiv.org/html/2606.31422#A1.SS2)\.

###### Proposition 5\.5\(Uncertainty\-only miscoverage\)\.

LetEt=\{i:bti≠gti\}E\_\{t\}=\\\{i:b\_\{t\}^\{i\}\\neq g\_\{t\}^\{i\}\\\}be the wrong\-belief set and letCt=\{i∈Et:confi​\(t\)≥α\}C\_\{t\}=\\\{i\\in E\_\{t\}:\\mathrm\{conf\}\_\{i\}\(t\)\\geq\\alpha\\\}be the confidently wrong subset\. If\|Ct\|/\|Et\|≥pcw\|C\_\{t\}\|/\|E\_\{t\}\|\\geq p\_\{\\mathrm\{cw\}\}and an uncertainty\-only policy probes only fields withconfi​\(t\)<α\\mathrm\{conf\}\_\{i\}\(t\)<\\alpha, then its one\-step wrong\-field recall obeys

Recallt=\|Et∖Ct\|\|Et\|≤1−pcw\(\|Et\|\>0\)\.\\mathrm\{Recall\}\_\{t\}=\\frac\{\|E\_\{t\}\\setminus C\_\{t\}\|\}\{\|E\_\{t\}\|\}\\leq 1\-p\_\{\\mathrm\{cw\}\}\\quad\(\|E\_\{t\}\|\>0\)\.\(15\)

##### Interpretation\.

Confidence is dangerous when wrong beliefs are confidently held: the selector excludes exactly the fields it most needs to repair\. Proof in Appendix Section[A\.3](https://arxiv.org/html/2606.31422#A1.SS3)\.

###### Proposition 5\.6\(Non\-adaptive allocation loss\)\.

Letqi=𝔼​\[G​\(\{i\}\)\]q\_\{i\}=\\mathbb\{E\}\[G\(\\\{i\\\}\)\]andq\(1\)≥⋯≥q\(n\)q\_\{\(1\)\}\\geq\\cdots\\geq q\_\{\(n\)\}be the sorted gains\. A uniform non\-adaptive single\-probe policy has expected gain

Gunif=q¯=1n​∑i=1nqi,G\_\{\\mathrm\{unif\}\}=\\bar\{q\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}q\_\{i\},\(16\)whereas the best targeted single probe has gainGtar=q\(1\)G\_\{\\mathrm\{tar\}\}=q\_\{\(1\)\}\. Its relative efficiency is

Effunif=GunifGtar=q¯q\(1\)<1\\mathrm\{Eff\}\_\{\\mathrm\{unif\}\}=\\frac\{G\_\{\\mathrm\{unif\}\}\}\{G\_\{\\mathrm\{tar\}\}\}=\\frac\{\\bar\{q\}\}\{q\_\{\(1\)\}\}<1\(17\)whenever the gains are not all equal\.

##### Interpretation\.

This is the mathematical reason periodic or random checks can look reasonable in average probe count yet weak in terminal accuracy: they ignore heterogeneity in which fields matter\. Proof in Appendix Section[A\.4](https://arxiv.org/html/2606.31422#A1.SS4)\.

### 5\.2Task\-Side Displacement

###### Lemma 5\.7\(Probe\-action displacement\)\.

LetPπP\_\{\\pi\}be the number of probes used by policyπ\\pi, so thatNπ=H−PπN\_\{\\pi\}=H\-P\_\{\\pi\}task\-action slots remain\. Suppose task success requires at leastKKeffective task actions and each task action is effective with probability at mostηπ\\eta\_\{\\pi\}\. Then

Pr⁡\[success​\(π\)\]≤𝔼​\[min⁡\(1,ηπ​NπK\)\]\.\\Pr\[\\mathrm\{success\}\(\\pi\)\]\\leq\\mathbb\{E\}\\\!\\left\[\\min\\\!\\left\(1,\\frac\{\\eta\_\{\\pi\}N\_\{\\pi\}\}\{K\}\\right\)\\right\]\.\(18\)IfPπP\_\{\\pi\}is deterministic, the bound becomesPr⁡\[success​\(π\)\]≤min⁡\(1,ηπ​\(H−Pπ\)/K\)\\Pr\[\\mathrm\{success\}\(\\pi\)\]\\leq\\min\(1,\\eta\_\{\\pi\}\(H\-P\_\{\\pi\}\)/K\)\.

##### Interpretation\.

The bound does not claim that probes are bad; it states the accounting identity that every probe must earn back the task action it displaces\. Proof in Appendix Section[A\.5](https://arxiv.org/html/2606.31422#A1.SS5)\.

###### Theorem 5\.8\(Probe\-action frontier\)\.

For a policyπ\\pi, letBT​\(π\)B\_\{T\}\(\\pi\)be the number of probes assigned to typeTT,Pπ=Bproc​\(π\)\+Bspat​\(π\)P\_\{\\pi\}=B\_\{\\mathrm\{proc\}\}\(\\pi\)\+B\_\{\\mathrm\{spat\}\}\(\\pi\), andλT=nT/n\\lambda\_\{T\}=n\_\{T\}/n\. Define the belief gain

ℬ​\(π\)=𝔼​\[AH​\(π\)\]−𝔼​\[AH​\(NoProbe\)\]\.\\mathcal\{B\}\(\\pi\)=\\mathbb\{E\}\[A\_\{H\}\(\\pi\)\]\-\\mathbb\{E\}\[A\_\{H\}\(\\mathrm\{NoProbe\}\)\]\.\(19\)Under Assumption[5\.1](https://arxiv.org/html/2606.31422#S5.Thmtheorem1)and Eq\. \([9](https://arxiv.org/html/2606.31422#S5.E9)\), any greedy score policy satisfies

ℬ​\(π\)\\displaystyle\\mathcal\{B\}\(\\pi\)≥∑T∈\{proc,spat\}λT​RT​\(π\),\\displaystyle\\geq\\sum\_\{T\\in\\\{\\mathrm\{proc\},\\mathrm\{spat\}\\\}\}\\lambda\_\{T\}R\_\{T\}\(\\pi\),\(20\)RT​\(π\)\\displaystyle R\_\{T\}\(\\pi\)=\(1−e−γT​\(ρ\)\)​GT​\(ST⋆​\(BT​\(π\)\)\)\.\\displaystyle=\\left\(1\-e^\{\-\\gamma\_\{T\}\(\\rho\)\}\\right\)G\_\{T\}\(S\_\{T\}^\{\\star\}\(B\_\{T\}\(\\pi\)\)\)\.At the same time, task success is bounded by

Pr⁡\[success​\(π\)\]≤𝔼​\[min⁡\(1,ηπ​\(H−Pπ\)K\)\]\.\\Pr\[\\mathrm\{success\}\(\\pi\)\]\\leq\\mathbb\{E\}\\\!\\left\[\\min\\\!\\left\(1,\\frac\{\\eta\_\{\\pi\}\(H\-P\_\{\\pi\}\)\}\{K\}\\right\)\\right\]\.\(21\)Consequently, whenGT​\(ST⋆​\(BT\)\)G\_\{T\}\(S\_\{T\}^\{\\star\}\(B\_\{T\}\)\)is strictly increasing for some type andηπ\\eta\_\{\\pi\}does not increase enough to offset the loss ofH−PπH\-P\_\{\\pi\}, varying the probe budget traces a Pareto frontier between terminal world\-model accuracy and task success\.

##### Interpretation\.

The frontier is not an empirical accident\. Eq\. \([20](https://arxiv.org/html/2606.31422#S5.E20)\) rewards well\-targeted information, while Eq\. \([21](https://arxiv.org/html/2606.31422#S5.E21)\) charges the same horizon for collecting it\. The right probe rate therefore depends on whether the downstream objective values calibrated beliefs, completed tasks, or a mixture of both\. Proof in Appendix Section[A\.6](https://arxiv.org/html/2606.31422#A1.SS6)\.

## 6Experiments

### 6\.1Experimental Setup

##### Environments\.

We evaluate in three controlled environments that expose gold field states, allowing us to measure belief drift directly rather than inferring it from task success\. This diagnostic design complements embodied, web, and long\-horizon benchmarks such as ALFWorld, ScienceWorld, WebArena, Mind2Web, AgentBench, and UltraHorizon\(Shridharet al\.,[2021](https://arxiv.org/html/2606.31422#bib.bib15); Wanget al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib25); Zhouet al\.,[2024b](https://arxiv.org/html/2606.31422#bib.bib16); Denget al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib17); Liuet al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib19); Luoet al\.,[2025](https://arxiv.org/html/2606.31422#bib.bib24)\)\.

ObjectStateWorldis a room\-and\-object task with mutable object locations and lock states\.ToolDAGWorldmodels API/tool workflows with prerequisite dependencies and mutable activation state, following the tool\-use motivation of Toolformer and ToolLLM\(Schicket al\.,[2023](https://arxiv.org/html/2606.31422#bib.bib12); Qinet al\.,[2024](https://arxiv.org/html/2606.31422#bib.bib13)\)\. It is dominated by procedural fields\.GraphNavWorldis a partially observable graph navigation task with exogenous edge mutations and is dominated by spatial fields\. Each environment exposes the same probe API: given a fieldii, the environment returnsgtig\_\{t\}^\{i\}and consumes one step, analogous to checking a database record, calling a status endpoint, or re\-opening an interface before a dependent action\.

##### Stress regimes\.

We evaluate low, medium, and high mutation regimes with average mutation ratesμ¯∈\{0\.02,0\.10,0\.30\}\\bar\{\\mu\}\\in\\\{0\.02,0\.10,0\.30\\\}\. The medium regime is the primary setting for all paired comparisons; the low\- and high\-stress regimes test whether the observed frontier is tied to a single mutation rate\.

##### Baselines\.

We compare seven strategies under the same budgetB=⌊H/4⌋B=\\lfloor H/4\\rfloor: No\-Probe, Random\-Probe, Periodic\-Probe, Self\-Uncertainty, EnvProbe\-Simple, EnvProbe\-Judge, and Oracle\-Probe\. Random and periodic policies test non\-adaptive allocation; Self\-Uncertainty tests whether verbalized confidence alone is enough, as commonly assumed by uncertainty\-sampling methods\(Lewis and Gale,[1994](https://arxiv.org/html/2606.31422#bib.bib26); Settles,[2009](https://arxiv.org/html/2606.31422#bib.bib27)\)\. Oracle\-Probe and Oracle\-TW are upper\-bound diagnostics that access gold mismatch\.

##### Metrics\.

World\-state accuracy \(WSA,AHA\_\{H\}\): fraction of belief fields matching gold at episode end; continuous in\[0,1\]\[0,1\];*primary metric*\.Task success \(TS\): binary episode completion; secondary\.Useful\-probe rate \(UPR\): fraction of probes that correct a wrong field\.Collapse onset \(τc\\tau\_\{c\}\): step at whichAtA\_\{t\}first falls below 0\.6\.

##### Statistics\.

All primary comparisons use paired seeds:n=220n=220for ToolDAGWorld,n=440n=440for the spatial pool, andn=660n=660when all environments are pooled\. Confidence intervals andpp\-values are computed with 10,000 paired bootstrap resamples\(Efron and Tibshirani,[1994](https://arxiv.org/html/2606.31422#bib.bib28)\); families of comparisons use Bonferroni correction\.

##### Agent\.

The main agent uses GPT\-4o mini through the OpenAI API\(OpenAI,[2024](https://arxiv.org/html/2606.31422#bib.bib29)\)\. Prompts elicit JSON belief updates, staleness estimatesτ^i\\hat\{\\tau\}\_\{i\}, and confidence estimatesconfi\\mathrm\{conf\}\_\{i\}at each step\. Implementation details are deferred to the appendix\.

### 6\.2Results

#### 6\.2\.1Result: Probing Repairs the World Model

Table 1:World\-state accuracy and probe\-action frontier\.The upper block compares EnvProbe\-Simple with Periodic\-Probe under paired seeds\. The lower block compares structural variants against the full score on ToolDAGWorld\. Task\-success differences use McNemar tests\.Stratum / ComparisonnnMethodAHA\_\{H\}ReferenceAHA\_\{H\}Δ^\\hat\{\\Delta\}\(pp\)95% CI \(pp\)ppTakeawayProcedural \(ToolDAGWorld\)2200\.4310\.313\+11\.76\+11\.76\[\+10\.77, \+12\.75\]<0\.001<0\.001targeted repairCombined \(all envs\)6600\.3710\.306\+6\.45\+6\.45\[\+5\.89, \+7\.02\]<0\.001<0\.001consistent gainSpatial \(Graph\+Object\)4400\.3410\.303\+3\.79\+3\.79\[\+3\.26, \+4\.34\]<0\.001<0\.001smaller but reliableProcedural variants vs\. full EnvProbe\-Simple;†task McNemar\(c\+d\)\(c\{\+\}d\)\-only vs\. SimpleAHA\_\{H\}2200\.4910\.431\+6\.03\+6\.03\[\+4\.87, \+7\.18\]<0\.001<0\.001task 15\.9% vs 20\.5% \(p†=0\.22p^\{\\dagger\}=0\.22\)−u\-u\(no uncertainty\) vs\. Simple2200\.4880\.431\+5\.76\+5\.76\[\+4\.57, \+6\.96\]<0\.001<0\.001task 8\.2% vs 20\.5% \(p†=0\.0001p^\{\\dagger\}=0\.0001\)

Table[1](https://arxiv.org/html/2606.31422#S6.T1)answers the first question: does querying the environment in the middle of planning reduce terminal world\-model error? Yes\. Relative to Periodic\-Probe, EnvProbe\-Simple improves end\-state accuracy on the procedural ToolDAGWorld stratum by\+11\.76\+11\.76points, and the gain remains positive when all environments are pooled\. The spatial gain is smaller, as predicted by Lemma[5\.4](https://arxiv.org/html/2606.31422#S5.Thmtheorem4): exogenous location and edge changes are less visible in the agent’s own self\-reports, so the selector has less useful signal to exploit\.

##### Pareto trade\-off and uncertainty anti\-signal\.

The same table also shows why belief accuracy cannot be the only metric\. On ToolDAGWorld, high\-value probes compete with a dependency chain that also needs action slots\. The structural score\(c\+d\)\(c\+d\)achieves the best observed procedural accuracy, while the full score completes fewer episodes than lighter probing policies\. Removinguiu\_\{i\}improves belief accuracy but pushes the policy to the belief\-heavy extreme, confirming that verbalized uncertainty can misallocate probes\.

![Refer to caption](https://arxiv.org/html/2606.31422v1/x3.png)Figure 3:Procedural Pareto frontier \(ToolDAGWorld,n=220n=220paired\)\.Each point is a probe policy or ablation; thexx\-axis is task success and theyy\-axis is world\-state accuracyAHA\_\{H\}\. Filled markers are nondominated under the two objectives, and hollow markers are dominated\. Structural, probe\-heavy methods occupy the high\-accuracy/low\-task region, while light\-probe policies occupy the high\-task/low\-accuracy region\. The frontier visualizes Theorem[5\.8](https://arxiv.org/html/2606.31422#S5.Thmtheorem8): probe actions can repair beliefs, but every probe spends a step that cannot advance the task\.

#### 6\.2\.2Result: Structural Cues Explain the Gains

Table 2:Adjacent method comparisons onAHA\_\{H\}in the medium\-stress regime\.The table compares neighboring policies in the expected accuracy ordering\. Two rows are marked diagnostic because implementation details of the scorer or oracle objective change their interpretation; these diagnostics motivate the task\-weighted oracle and the normalized useful\-probe metric reported in the additional\-experiment appendix\.Table[2](https://arxiv.org/html/2606.31422#S6.T2)shows that method ordering is not monotone in probe count\. The reliable jump is from non\-targeted periodic probing to EnvProbe\-Simple on procedural fields\. Judge helps in some procedural cases because the extra model can interpret dependency context, but the main story is already visible in the explicit score: probes are useful when they are aimed at fields that block future actions\. The oracle rows are diagnostic rather than deployable, because an unweighted oracle can correct many mismatches that do not matter for the next action\.

#### 6\.2\.3Secondary Metrics

##### Collapse\-onset delay\.

The procedural setting gives a non\-degenerate world\-accuracy trajectory: EnvProbe\-Simple delays collapse fromτc=1\.68\\tau\_\{c\}=1\.68under Periodic\-Probe toτc=7\.48\\tau\_\{c\}=7\.48\(Δ^=\+5\.80\\hat\{\\Delta\}=\+5\.80steps,p<0\.001p<0\.001\)\. Spatial collapse onset is saturated in this protocol because many spatial fields begin below the fixed accuracy threshold; Figure[4](https://arxiv.org/html/2606.31422#S6.F4)shows this diagnostic and explains why collapse onset is used as supporting evidence rather than a primary spatial claim\.

![Refer to caption](https://arxiv.org/html/2606.31422v1/x4.png)Figure 4:World\-state accuracy trajectories\.The curves showAtA\_\{t\}over the episode for the medium\-stress regime\. ToolDAGWorld has a non\-degenerate collapse trajectory: EnvProbe\-Simple delays the first crossing of theAt<0\.6A\_\{t\}<0\.6threshold relative to Periodic\-Probe\. GraphNavWorld and ObjectStateWorld start near or below the same threshold for many methods, so collapse\-onset is saturated and less informative for spatial analysis\.
##### Drift before action collapse\.

On spatial episodes \(n=2,210n=2\{,\}210\), world\-state drift precedes action\-validity collapse by\+2\.422\+2\.422steps on average \(p=0\.0001p=0\.0001\)\. On procedural episodes, action invalidity can occur before the aggregate world\-state threshold is crossed, because a single wrong tool\-precondition belief can invalidate the next call\. A timing breakdown appears in Appendix[G](https://arxiv.org/html/2606.31422#A7); Figure[5](https://arxiv.org/html/2606.31422#S6.F5)visualizes the spatial timing pattern directly\.

![Refer to caption](https://arxiv.org/html/2606.31422v1/x5.png)Figure 5:Drift precedes collapse on spatial episodes\.Scatter ofτd\\tau\_\{d\}\(firstAt<0\.6A\_\{t\}<0\.6,xx\-axis\) vs\.τc\\tau\_\{c\}\(first action\-validity<0\.6<0\.6,yy\-axis\) per episode\. Points below diagonal are drift\-first episodes\. In the spatial subset, drift comes first in 49% of episodes and action collapse comes first in 1\.3%\. The mean offset isτ¯c−τ¯d=\+2\.42\\bar\{\\tau\}\_\{c\}\-\\bar\{\\tau\}\_\{d\}=\+2\.42steps \(n=2,210n=2\{,\}210\); the plotted pilot scatter containsn=121n=121episodes\.
##### Useful\-probe rate\.

Raw UPR is distorted by selective triggering and oracle fallback behavior; budget\-normalizedUPR~\\widetilde\{\\mathrm\{UPR\}\}recovers the predicted ordering \(Tables[5](https://arxiv.org/html/2606.31422#A6.T5)and[6](https://arxiv.org/html/2606.31422#A6.T6)in the appendix\)\.

##### Confident\-wrong guardrail \(pcwp\_\{\\mathrm\{cw\}\}\)\.

The logs contain many high\-confidence wrong beliefs:p^cw=0\.940\\hat\{p\}\_\{\\mathrm\{cw\}\}=0\.940\[0\.933,0\.9470\.933,0\.947\] on the main scan, with pilot and false\-positive audits at0\.9240\.924and0\.9910\.991\. Proposition[5\.5](https://arxiv.org/html/2606.31422#S5.Thmtheorem5)explains why Self\-Uncertainty misses such fields by construction; Table[7](https://arxiv.org/html/2606.31422#A6.T7)reports the estimator audit\.

##### Component ablation\.

Table[3](https://arxiv.org/html/2606.31422#S6.T3)and Figure[6](https://arxiv.org/html/2606.31422#S6.F6)give the mechanism\. Removing criticality or dependency sharply reduces accuracy, establishing them as the load\-bearing structural terms\. Staleness is weakly useful\. Removing uncertainty improvesAHA\_\{H\}but worsens task success, which is exactly the pattern expected when confidence is a noisy probe\-routing signal rather than a calibrated estimate of environment error\.

Table 3:Component ablation on ToolDAGWorld\(n=220n=220paired\)\.Δ^​AH\\hat\{\\Delta\}A\_\{H\}= change inAHA\_\{H\}vs\. full 4\-dim baseline \(0\.4310\.431\)\. Positive values indicate that removing the component improves accuracy; negative values indicate that the component is load\-bearing\. Task\-success differences are evaluated by two\-sided McNemar tests\.![Refer to caption](https://arxiv.org/html/2606.31422v1/x6.png)Figure 6:Component ablation on ToolDAGWorld\.Blue/teal bars reportAHA\_\{H\}and amber bars report task success\. Removing criticality or dependency lowersAHA\_\{H\}, showing that these structural terms are load\-bearing\. Removing uncertainty raisesAHA\_\{H\}to0\.4880\.488but drops task success to8\.2%8\.2\\%, exposing the belief\-heavy extreme\. The\(c\+d\)\(c\+d\)rule gives the best observedAHA\_\{H\}in this ablation \(0\.4910\.491\) with task success statistically comparable to the full score\.

## 7Discussion

Probe\-action budget trade\-off\.The procedural results expose the budget constraint directly\. The policies that repair belief state most aggressively spend probes on the right fields, but those same probes consume horizon steps that could have advanced the task\. This is why\(c\+d\)\(c\+d\)reaches the highest observedAHA\_\{H\}, whereas Periodic\-Probe keeps the best task success among the non\-ablated baselines\. The theorem should be read in that light: probing helps when corrected state is useful downstream, but its rate must be set against the actions needed to finish the task\.

##### Spatial vs\. procedural asymmetry\.

The same budget behaves differently on spatial tasks\. Spatial chains are shorter, and exogenous location or edge changes leave weak traces in the LLM’s action history\. Self\-reported uncertainty therefore adds little, while the structural terms still identify fields worth checking\. Figure[7](https://arxiv.org/html/2606.31422#S7.F7)shows the result: the procedural frontier collapses into a dominance relation for the spatial regime\.

![Refer to caption](https://arxiv.org/html/2606.31422v1/x7.png)Figure 7:Spatial Pareto frontier \(GraphNavWorld \+ ObjectStateWorld,n=440n=440paired\)\.Contrast with Figure[3](https://arxiv.org/html/2606.31422#S6.F3): the procedural Pareto trade\-off vanishes on spatial belief\.\(c\+d\)\(c\{\+\}d\)\-only Pareto\-dominates all baselines on bothAHA\_\{H\}and task success simultaneously\. Spatial chains are shorter \(3–5 transitions vs\. 9 for ToolDAGWorld\), so the probe cost is small relative to the belief\-accuracy gain\.
##### Component\-level interpretation\.

The ablation explains why the full score is not the best belief\-accuracy policy\. Criticality and dependency carry most of the useful signal; staleness helps only modestly, and uncertainty is harmful in the procedural setting\. This matches prior calibration results showing that confidence estimates need not remain reliable decision signals under distribution shift\(Guoet al\.,[2017](https://arxiv.org/html/2606.31422#bib.bib39); Kadavathet al\.,[2022](https://arxiv.org/html/2606.31422#bib.bib40)\)\. A practical rule follows: use structural probe scores when a downstream planner will consume the repaired belief state, and lower the probe budget when task completion is the binding objective\.

## 8Conclusion

EnvProbe treats active environment queries as budgeted calibration for explicit world models\. A probe can reduce terminal world\-model error when it checks a structurally important field, but it can also displace a task action\. In our experiments, the structural\(c\+d\)\(c\+d\)variant is the strongest belief\-accuracy policy and Pareto\-dominates on spatial tasks, while verbalized uncertainty is an anti\-signal on procedural fields\. Probe policies should therefore be type\-aware: query beliefs that matter for the next plan, and set the probe rate against the downstream objective\.

## Broader Impact

EnvProbe can reduce undetected belief drift in long\-horizon LLM agents, with direct relevance to software automation, API orchestration, and database management\. Even Oracle\-Probe achievesAHOr<1A\_\{H\}^\{\\mathrm\{Or\}\}<1, so safety\-critical deployments still require safeguards beyond EnvProbe\. Code and environments are available open\-source\.

## References

- M\. Ahn, A\. Brohan, N\. Brown, Y\. Chebotar, O\. Cortes, B\. David, C\. Finn, C\. Fu, K\. Gopalakrishnan, K\. Hausman, A\. Herzog, D\. Ho, J\. Hsu, J\. Ibarz, B\. Ichter, A\. Irpan, E\. Jang, R\. J\. Ruano, K\. Jeffrey, S\. Jesmonth, N\. J\. Joshi, R\. Julian, D\. Kalashnikov, Y\. Kuang, K\. Lee, S\. Levine, Y\. Lu, L\. Luu, C\. Parada, P\. Pastor, J\. Quiambao, K\. Rao, J\. Rettinghouse, D\. Reyes, P\. Sermanet, N\. Sievers, C\. Tan, A\. Toshev, V\. Vanhoucke, F\. Xia, T\. Xiao, P\. Xu, S\. Xu, M\. Yan, and A\. Zeng \(2022\)Do as i can, not as i say: grounding language in robotic affordances\.arXiv preprint arXiv:2204\.01691\.External Links:2204\.01691,[Link](https://arxiv.org/abs/2204.01691)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1)\.
- Bayesian experimental design: a review\.Statistical Science10\(3\),pp\. 273–304\.External Links:[Document](https://dx.doi.org/10.1214/ss/1177009939)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p3.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px2.p1.1)\.
- X\. Deng, Y\. Gu, B\. Zheng, S\. Chen, S\. Stevens, B\. Wang, H\. Sun, and Y\. Su \(2023\)Mind2Web: towards a generalist agent for the web\.InAdvances in Neural Information Processing Systems \(NeurIPS\),External Links:2306\.06070,[Link](https://arxiv.org/abs/2306.06070)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px4.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px1.p1.1)\.
- V\. Dongre, X\. Yang, E\. C\. Acikgoz, S\. Dey, G\. Tur, and D\. Hakkani\-Tur \(2024\)ReSpAct: harmonizing reasoning, speaking, and acting towards building large language model\-based conversational AI agents\.arXiv preprint arXiv:2411\.00927\.External Links:2411\.00927,[Link](https://arxiv.org/abs/2411.00927)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p4.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px3.p1.1)\.
- B\. Efron and R\. J\. Tibshirani \(1994\)An introduction to the bootstrap\.Chapman and Hall/CRC\.External Links:[Document](https://dx.doi.org/10.1201/9780429246593)Cited by:[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px5.p1.4)\.
- D\. C\. Fang and T\. Ke \(2025\)Information seeking for robust decision making under partial observability\.arXiv preprint arXiv:2510\.01531\.External Links:2510\.01531,[Link](https://arxiv.org/abs/2510.01531)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p4.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px3.p1.1)\.
- D\. Golovin and A\. Krause \(2011\)Adaptive submodularity: theory and applications in active learning and stochastic optimization\.Journal of Artificial Intelligence Research42,pp\. 427–486\.External Links:[Document](https://dx.doi.org/10.1613/jair.3278),1003\.3967,[Link](https://arxiv.org/abs/1003.3967)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p3.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px2.p1.1),[Assumption 5\.1](https://arxiv.org/html/2606.31422#S5.Thmtheorem1.p1.4.1)\.
- C\. Guo, G\. Pleiss, Y\. Sun, and K\. Q\. Weinberger \(2017\)On calibration of modern neural networks\.InProceedings of the 34th International Conference on Machine Learning \(ICML\),pp\. 1321–1330\.External Links:1706\.04599,[Link](https://arxiv.org/abs/1706.04599)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p3.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px3.p1.1),[§3](https://arxiv.org/html/2606.31422#S3.SS0.SSS0.Px2.p1.1),[§7](https://arxiv.org/html/2606.31422#S7.SS0.SSS0.Px2.p1.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 LLMs\.InAdvances in Neural Information Processing Systems \(NeurIPS\),External Links:2402\.03271,[Link](https://arxiv.org/abs/2402.03271)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p4.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px3.p1.1)\.
- W\. Huang, F\. Xia, T\. Xiao, H\. Chan, J\. Liang, P\. Florence, A\. Zeng, J\. Tompson, I\. Mordatch, Y\. Chebotar, P\. Sermanet, N\. Brown, T\. Jackson, L\. Luu, S\. Levine, K\. Hausman, and B\. Ichter \(2022\)Inner monologue: embodied reasoning through planning with language models\.InConference on Robot Learning \(CoRL\),External Links:2207\.05608,[Link](https://arxiv.org/abs/2207.05608)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Kadavath, T\. Conerly, A\. Askell, T\. Henighan, D\. Drain, E\. Perez, N\. Schiefer, Z\. Hatfield\-Dodds, N\. DasSarma, E\. Tran\-Johnson, S\. Johnston, S\. El\-Showk, A\. Jones, N\. Elhage, T\. Hume, A\. Chen, Y\. Bai, S\. Bowman, S\. Fort, D\. Ganguli, D\. Hernandez, J\. Jacobson, J\. Kernion, S\. Kravec, L\. Lovitt, K\. Ndousse, C\. Olsson, S\. Ringer, D\. Amodei, T\. Brown, J\. Clark, N\. Joseph, B\. Mann, S\. McCandlish, C\. Olah, and J\. Kaplan \(2022\)Language models \(mostly\) know what they know\.arXiv preprint arXiv:2207\.05221\.External Links:2207\.05221,[Link](https://arxiv.org/abs/2207.05221)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p3.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px3.p1.1),[§3](https://arxiv.org/html/2606.31422#S3.SS0.SSS0.Px2.p1.1),[§7](https://arxiv.org/html/2606.31422#S7.SS0.SSS0.Px2.p1.1)\.
- L\. P\. Kaelbling, M\. L\. Littman, and A\. R\. Cassandra \(1998\)Planning and acting in partially observable stochastic domains\.Artificial Intelligence101\(1–2\),pp\. 99–134\.External Links:[Document](https://dx.doi.org/10.1016/S0004-3702%2898%2900023-X)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p3.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px2.p1.1)\.
- J\. Y\. Koh, R\. Lo, L\. Jang, V\. Duvvur, M\. C\. Lim, P\. Huang, G\. Neubig, S\. Zhou, R\. Salakhutdinov, and D\. Fried \(2024\)VisualWebArena: evaluating multimodal agents on realistic visual web tasks\.arXiv preprint arXiv:2401\.13649\.External Links:2401\.13649,[Link](https://arxiv.org/abs/2401.13649)Cited by:[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px4.p1.1)\.
- A\. Krause and D\. Golovin \(2014\)Submodular function maximization\.InTractability: Practical Approaches to Hard Problems,L\. Bordeaux, Y\. Hamadi, and P\. Kohli \(Eds\.\),pp\. 71–104\.Cited by:[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px2.p1.1),[Assumption 5\.1](https://arxiv.org/html/2606.31422#S5.Thmtheorem1.p1.4.1)\.
- D\. D\. Lewis and W\. A\. Gale \(1994\)A sequential algorithm for training text classifiers\.InProceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,pp\. 3–12\.External Links:[Document](https://dx.doi.org/10.1007/978-1-4471-2099-5%5F1)Cited by:[§3](https://arxiv.org/html/2606.31422#S3.SS0.SSS0.Px2.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px3.p1.1)\.
- X\. Liu, H\. Yu, H\. Zhang, Y\. Xu, X\. Lei, H\. Lai, Y\. Gu, H\. Ding, K\. Men, K\. Yang, S\. Zhang, X\. Deng, A\. Zeng, Z\. Du, C\. Zhang, S\. Shen, T\. Zhang, Y\. Su, H\. Sun, M\. Huang, Y\. Dong, and J\. Tang \(2023\)AgentBench: evaluating LLMs as agents\.arXiv preprint arXiv:2308\.03688\.External Links:2308\.03688,[Link](https://arxiv.org/abs/2308.03688)Cited by:[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px4.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px1.p1.1)\.
- H\. Luo, H\. Zhang, X\. Zhang, H\. Wang, Z\. Qin, W\. Lu,et al\.\(2025\)UltraHorizon: benchmarking agent capabilities in ultra long\-horizon scenarios\.arXiv preprint arXiv:2509\.21766\.External Links:2509\.21766,[Link](https://arxiv.org/abs/2509.21766)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§1](https://arxiv.org/html/2606.31422#S1.p2.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px4.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px1.p1.1)\.
- G\. L\. Nemhauser, L\. A\. Wolsey, and M\. L\. Fisher \(1978\)An analysis of approximations for maximizing submodular set functions—I\.Mathematical Programming14\(1\),pp\. 265–294\.Note:Greedy\(1−1/e\)\(1\-1/e\)approximation for monotone submodular maximization under cardinality constraint\.External Links:[Document](https://dx.doi.org/10.1007/BF01588971)Cited by:[Assumption 5\.1](https://arxiv.org/html/2606.31422#S5.Thmtheorem1.p1.4.1)\.
- OpenAI \(2024\)GPT\-4o mini: advancing cost\-efficient intelligence\.Note:[https://openai\.com/index/gpt\-4o\-mini\-advancing\-cost\-efficient\-intelligence/](https://openai.com/index/gpt-4o-mini-advancing-cost-efficient-intelligence/)Accessed 2026\-06\-26Cited by:[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px6.p1.2)\.
- Y\. Qin, S\. Liang, Y\. Ye, K\. Zhu, L\. Yan, Y\. Lu, Y\. Lin, X\. Cong, X\. Tang, B\. Qian, S\. Zhao, L\. Hong, R\. Tian, R\. Xie, J\. Zhou, M\. Gerstein, D\. Li, Z\. Liu, and M\. Sun \(2024\)ToolLLM: facilitating large language models to master 16000\+ real\-world APIs\.InInternational Conference on Learning Representations \(ICLR\),External Links:2307\.16789,[Link](https://arxiv.org/abs/2307.16789)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px1.p2.2)\.
- S\. Ross, J\. Pineau, S\. Paquet, and B\. Chaib\-draa \(2008\)Online planning algorithms for POMDPs\.Journal of Artificial Intelligence Research32,pp\. 663–704\.External Links:[Document](https://dx.doi.org/10.1613/jair.2567)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p3.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px2.p1.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 \(NeurIPS\),External Links:2302\.04761,[Link](https://arxiv.org/abs/2302.04761)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px1.p2.2)\.
- B\. Settles \(2009\)Active learning literature survey\.Technical reportTechnical Report1648,University of Wisconsin–Madison\.External Links:[Link](https://burrsettles.com/pub/settles.activelearning.pdf)Cited by:[§3](https://arxiv.org/html/2606.31422#S3.SS0.SSS0.Px2.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px3.p1.1)\.
- N\. Shinn, F\. Cassano, A\. Gopinath, K\. R\. Narasimhan, and S\. Yao \(2023\)Reflexion: language agents with verbal reinforcement learning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),External Links:2303\.11366,[Link](https://arxiv.org/abs/2303.11366),[Document](https://dx.doi.org/10.52202/075280-0377)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§1](https://arxiv.org/html/2606.31422#S1.p4.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1),[§4\.2](https://arxiv.org/html/2606.31422#S4.SS2.SSS0.Px2.p1.1)\.
- M\. Shridhar, X\. Yuan, M\. Côté, Y\. Bisk, A\. Trischler, and M\. Hausknecht \(2021\)ALFWorld: aligning text and embodied environments for interactive learning\.InInternational Conference on Learning Representations \(ICLR\),External Links:2010\.03768,[Link](https://arxiv.org/abs/2010.03768)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px4.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px1.p1.1)\.
- G\. Wang, Y\. Xie, Y\. Jiang, A\. Mandlekar, C\. Xiao, Y\. Zhu, L\. Fan, and A\. Anandkumar \(2024\)Voyager: an open\-ended embodied agent with large language models\.Transactions on Machine Learning Research \(TMLR\)\.External Links:2305\.16291,[Link](https://arxiv.org/abs/2305.16291)Cited by:[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1)\.
- R\. Wang, P\. Jansen, M\. Côté, and P\. Ammanabrolu \(2022\)ScienceWorld: is your agent smarter than a 5th grader?\.InProceedings of the 2022 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),pp\. 11279–11298\.External Links:2203\.07540,[Link](https://arxiv.org/abs/2203.07540)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px1.p1.1)\.
- Z\. Wang, F\. Wu, H\. Wang, X\. Tang, B\. Li, and Z\. Yin \(2026\)Why reasoning fails to plan: a planning\-centric analysis of long\-horizon decision making in LLM agents\.arXiv preprint arXiv:2601\.22311\.External Links:2601\.22311,[Link](https://arxiv.org/abs/2601.22311)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p2.1)\.
- S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. R\. Narasimhan, and Y\. Cao \(2023\)ReAct: synergizing reasoning and acting in language models\.InInternational Conference on Learning Representations \(ICLR\),External Links:2210\.03629,[Link](https://arxiv.org/abs/2210.03629)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1)\.
- X\. Yin and H\. Du \(2026\)GLOVE: global verifier for LLM memory\-environment realignment\.arXiv preprint arXiv:2601\.19249\.External Links:2601\.19249,[Link](https://arxiv.org/abs/2601.19249)Cited by:[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1)\.
- Z\. Yuan, S\. Yuan, and L\. Xie \(2026\)RPMS: enhancing llm\-based embodied planning through rule\-augmented memory synergy\.External Links:2603\.17831,[Link](https://arxiv.org/abs/2603.17831)Cited by:[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Zhou, K\. Yan, M\. Shlapentokh\-Rothman, H\. Wang, and Y\. Wang \(2024a\)Language agent tree search unifies reasoning acting and planning in language models\.InInternational Conference on Machine Learning \(ICML\),External Links:2310\.04406,[Link](https://arxiv.org/abs/2310.04406),[Document](https://dx.doi.org/10.48550/arXiv.2310.04406)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1),[§4\.2](https://arxiv.org/html/2606.31422#S4.SS2.SSS0.Px2.p1.1)\.
- S\. Zhou, F\. F\. Xu, H\. Zhu, X\. Zhou, R\. Lo, A\. Sridhar, X\. Cheng, T\. Ou, Y\. Bisk, D\. Fried, U\. Alon, and G\. Neubig \(2024b\)WebArena: a realistic web environment for building autonomous agents\.InInternational Conference on Learning Representations \(ICLR\),External Links:2307\.13854,[Link](https://arxiv.org/abs/2307.13854)Cited by:[§1](https://arxiv.org/html/2606.31422#S1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2606.31422#S2.SS0.SSS0.Px4.p1.1),[§6\.1](https://arxiv.org/html/2606.31422#S6.SS1.SSS0.Px1.p1.1)\.

## Appendix AProofs

We provide proof details for the statements in Section[5](https://arxiv.org/html/2606.31422#S5)\.

### A\.1Proof of Lemma[5\.3](https://arxiv.org/html/2606.31422#S5.Thmtheorem3)

LetSjS\_\{j\}be the set selected afterjjprobes of typeTT, and letST⋆S\_\{T\}^\{\\star\}be the optimal set with\|ST⋆\|≤BT\|S\_\{T\}^\{\\star\}\|\\leq B\_\{T\}\. By monotonicity and submodularity,

maxi∈ℱT∖Sj⁡ΔT​\(i∣Sj\)≥GT​\(ST⋆\)−GT​\(Sj\)BT\.\\max\_\{i\\in\\mathcal\{F\}\_\{T\}\\setminus S\_\{j\}\}\\Delta\_\{T\}\(i\\mid S\_\{j\}\)\\geq\\frac\{G\_\{T\}\(S\_\{T\}^\{\\star\}\)\-G\_\{T\}\(S\_\{j\}\)\}\{B\_\{T\}\}\.\(22\)The marginal\-quality condition in Definition[5\.2](https://arxiv.org/html/2606.31422#S5.Thmtheorem2)gives

𝔼​\[GT​\(Sj\+1\)−GT​\(Sj\)∣Sj\]\\displaystyle\\mathbb\{E\}\[G\_\{T\}\(S\_\{j\+1\}\)\-G\_\{T\}\(S\_\{j\}\)\\mid S\_\{j\}\]\(23\)≥γTBT​\(GT​\(ST⋆\)−GT​\(Sj\)\)\.\\displaystyle\\qquad\\geq\\frac\{\\gamma\_\{T\}\}\{B\_\{T\}\}\\left\(G\_\{T\}\(S\_\{T\}^\{\\star\}\)\-G\_\{T\}\(S\_\{j\}\)\\right\)\.LetRj=GT​\(ST⋆\)−𝔼​\[GT​\(Sj\)\]R\_\{j\}=G\_\{T\}\(S\_\{T\}^\{\\star\}\)\-\\mathbb\{E\}\[G\_\{T\}\(S\_\{j\}\)\]\. Taking expectations yieldsRj\+1≤\(1−γT/BT\)​RjR\_\{j\+1\}\\leq\(1\-\\gamma\_\{T\}/B\_\{T\}\)R\_\{j\}\. Iterating forBTB\_\{T\}steps,

RBT≤\(1−γTBT\)BT​GT​\(ST⋆\)≤e−γT​GT​\(ST⋆\)\.R\_\{B\_\{T\}\}\\leq\\left\(1\-\\frac\{\\gamma\_\{T\}\}\{B\_\{T\}\}\\right\)^\{B\_\{T\}\}G\_\{T\}\(S\_\{T\}^\{\\star\}\)\\leq e^\{\-\\gamma\_\{T\}\}G\_\{T\}\(S\_\{T\}^\{\\star\}\)\.\(24\)Rearranging proves the claim\.

### A\.2Proof of Lemma[5\.4](https://arxiv.org/html/2606.31422#S5.Thmtheorem4)

Writem​\(h,z\)=𝔼​\[Δi​\(t\)∣hi​\(t\)=h,zi​\(t\)=z\]m\(h,z\)=\\mathbb\{E\}\[\\Delta\_\{i\}\(t\)\\mid h\_\{i\}\(t\)=h,z\_\{i\}\(t\)=z\]andm0​\(h\)=𝔼​\[Δi​\(t\)∣hi​\(t\)=h\]m\_\{0\}\(h\)=\\mathbb\{E\}\[\\Delta\_\{i\}\(t\)\\mid h\_\{i\}\(t\)=h\]\. By assumption,\|m​\(h,z\)−m0​\(h\)\|≤εspat\|m\(h,z\)\-m\_\{0\}\(h\)\|\\leq\\varepsilon\_\{\\mathrm\{spat\}\}for every field\. Letizi\_\{z\}be the best field selected by any rule that may use bothhhandzz, and leti0i\_\{0\}be the best structural field usinghhalone\. Then

m​\(hiz,ziz\)\\displaystyle m\(h\_\{i\_\{z\}\},z\_\{i\_\{z\}\}\)≤m0​\(hiz\)\+εspat\\displaystyle\\leq m\_\{0\}\(h\_\{i\_\{z\}\}\)\+\\varepsilon\_\{\\mathrm\{spat\}\}\(25\)≤m0​\(hi0\)\+εspat\\displaystyle\\leq m\_\{0\}\(h\_\{i\_\{0\}\}\)\+\\varepsilon\_\{\\mathrm\{spat\}\}\(26\)≤m​\(hi0,zi0\)\+2​εspat\.\\displaystyle\\leq m\(h\_\{i\_\{0\}\},z\_\{i\_\{0\}\}\)\+2\\varepsilon\_\{\\mathrm\{spat\}\}\.\(27\)Thus adding self\-report features can improve expected one\-step gain by at most2​εspat2\\varepsilon\_\{\\mathrm\{spat\}\}in the spatial regime\. If a particular linear score usingzzselects a worse field thani0i\_\{0\}, the difference is precisely its ranking regret\.

### A\.3Proof of Proposition[5\.5](https://arxiv.org/html/2606.31422#S5.Thmtheorem5)

Self\-Uncertainty is allowed to probe only fields with confidence belowα\\alpha\. Every field inCtC\_\{t\}is wrong but has confidence at leastα\\alpha, so none of these fields is eligible for selection\. Since\|Ct\|/\|Et\|≥pcw\|C\_\{t\}\|/\|E\_\{t\}\|\\geq p\_\{\\mathrm\{cw\}\}, at most a\(1−pcw\)\(1\-p\_\{\\mathrm\{cw\}\}\)fraction of wrong fields can be recalled by such a selector in that step\.

### A\.4Proof of Proposition[5\.6](https://arxiv.org/html/2606.31422#S5.Thmtheorem6)

Under uniform non\-adaptive sampling, the expected gain of a single probe isn−1​∑iqi=q¯n^\{\-1\}\\sum\_\{i\}q\_\{i\}=\\bar\{q\}\. A targeted selector with access to the gain ordering chooses the top field and obtainsq\(1\)q\_\{\(1\)\}\. The relative efficiency is thereforeq¯/q\(1\)\\bar\{q\}/q\_\{\(1\)\}\. If gains are not all equal,q¯<q\(1\)\\bar\{q\}<q\_\{\(1\)\}\.

### A\.5Proof of Lemma[5\.7](https://arxiv.org/html/2606.31422#S5.Thmtheorem7)

Condition onNπN\_\{\\pi\}, the number of task\-action slots left after probing\. LetMMbe the number of effective task actions\. By assumption,𝔼​\[M∣Nπ\]≤ηπ​Nπ\\mathbb\{E\}\[M\\mid N\_\{\\pi\}\]\\leq\\eta\_\{\\pi\}N\_\{\\pi\}\. Since task success requiresM≥KM\\geq K, Markov’s inequality gives

Pr⁡\[success​\(π\)∣Nπ\]\\displaystyle\\Pr\[\\mathrm\{success\}\(\\pi\)\\mid N\_\{\\pi\}\]≤Pr⁡\[M≥K∣Nπ\]\\displaystyle\\leq\\Pr\[M\\geq K\\mid N\_\{\\pi\}\]\(28\)≤min⁡\(1,ηπ​NπK\)\.\\displaystyle\\leq\\min\\\!\\left\(1,\\frac\{\\eta\_\{\\pi\}N\_\{\\pi\}\}\{K\}\\right\)\.Taking expectation overNπN\_\{\\pi\}proves the first statement\. The deterministicPπP\_\{\\pi\}case follows by substitutingNπ=H−PπN\_\{\\pi\}=H\-P\_\{\\pi\}\.

### A\.6Proof of Theorem[5\.8](https://arxiv.org/html/2606.31422#S5.Thmtheorem8)

Apply Lemma[5\.3](https://arxiv.org/html/2606.31422#S5.Thmtheorem3)separately toT∈\{proc,spat\}T\\in\\\{\\mathrm\{proc\},\\mathrm\{spat\}\\\}\. SinceAH=∑TλT​AHTA\_\{H\}=\\sum\_\{T\}\\lambda\_\{T\}A\_\{H\}^\{T\}withλT=nT/n\\lambda\_\{T\}=n\_\{T\}/n, linearity of expectation gives

ℬ​\(π\)\\displaystyle\\mathcal\{B\}\(\\pi\)=∑TλT​𝔼​\[GT​\(Sρ,T\)\]\\displaystyle=\\sum\_\{T\}\\lambda\_\{T\}\\mathbb\{E\}\[G\_\{T\}\(S\_\{\\rho,T\}\)\]\(29\)≥∑TλT​\(1−e−γT​\(ρ\)\)​GT​\(ST⋆​\(BT​\(π\)\)\)\.\\displaystyle\\geq\\sum\_\{T\}\\lambda\_\{T\}\(1\-e^\{\-\\gamma\_\{T\}\(\\rho\)\}\)G\_\{T\}\(S\_\{T\}^\{\\star\}\(B\_\{T\}\(\\pi\)\)\)\.This is Eq\. \([20](https://arxiv.org/html/2606.31422#S5.E20)\)\. Lemma[5\.7](https://arxiv.org/html/2606.31422#S5.Thmtheorem7)gives Eq\. \([21](https://arxiv.org/html/2606.31422#S5.E21)\) after substitutingPπ=Bproc​\(π\)\+Bspat​\(π\)P\_\{\\pi\}=B\_\{\\mathrm\{proc\}\}\(\\pi\)\+B\_\{\\mathrm\{spat\}\}\(\\pi\)\. If increasingBTB\_\{T\}strictly increases the oracle repair gain for some type, the belief bound moves upward\. The same increase also weakly decreasesH−PπH\-P\_\{\\pi\}; therefore the task\-success bound moves downward unlessηπ\\eta\_\{\\pi\}increases enough to offset the lost task\-action slots\. The two objectives are therefore not jointly monotone in the probe budget, which yields the claimed Pareto frontier\.

## Appendix BImplementation Details

##### Environments\.

All three environments are implemented in Python with deterministic seeding\. Gold\-state trajectories are stored as JSONL files with full field\-level provenance\. Episode seeds span\[0,219\]\[0,219\]for the main paired cells; low\- and high\-stress regime checks use disjoint held\-out seeds\.

##### Hyperparameters\.

Probe thresholdρ⋆=1\.5\\rho\_\{\\star\}=1\.5; horizonH∈\{20,30,40\}H\\in\\\{20,30,40\\\}for low/medium/high complexity; budgetB=⌊H/4⌋B=\\lfloor H/4\\rfloor; staleness normalization divisor=10=10\. Full hyperparameter table in Table[4](https://arxiv.org/html/2606.31422#A2.T4)\.

Table 4:Hyperparameter configuration for main results\.
##### Reproducibility\.

All episodes are deterministic given the tuple \(seed, environment, method\)\. The released code stores gold\-state trajectories and belief snapshots so that world\-state accuracy, useful\-probe rate, and collapse timing can be recomputed from raw logs\.

## Appendix CDataset and Environment Details

ObjectStateWorld contains object\-location, lock\-state, and inventory fields\. GraphNavWorld contains node\-location and dynamic\-edge fields\. ToolDAGWorld contains tool\-loaded, dependency\-satisfied, and subgoal\-complete fields\. Each environment defines a gold transition kernel, an agent\-facing textual observation, and a probe API that returns the current value of a requested field\. Procedural purity is highest in ToolDAGWorld, while the spatial pool contains fields whose mutations are exogenous to the action trace\.

## Appendix DFailure Case Analysis

A typical procedural failure occurs when a high\-uncertainty but low\-criticality field receives a probe before the tool\-precondition field that blocks the next API call\. The probe improves local belief accuracy but leaves too few actions to complete the dependency chain\. A typical spatial failure occurs when reported staleness is high for a field that has not actually mutated; the probe is correct but unhelpful, while an exogenously changed object\-location field remains stale\. These cases motivate the structural\(c\+d\)\(c\+d\)variant: dependency role and criticality are more stable signals than verbalized uncertainty or self\-reported recency\.

## Appendix EBroader Impact

*See also the main\-paper broader impact statement\.*

EnvProbe’s primary application is improving the reliability of LLM agents in long\-horizon automated tasks\. Improved reliability reduces costly action errors in deployments such as software workflows, database manipulation, and API orchestration\. The main societal benefit is reduced agent failure cost in production systems\. One concern is that more reliable agents may be deployed in higher\-stakes settings \(medical decision support, financial automation\) without adequate human oversight; we emphasize that Oracle\-Probe’s upper bound in our experiments still leaves substantial accuracy gaps \(AHOr<1A\_\{H\}^\{\\mathrm\{Or\}\}<1\), and no version of EnvProbe eliminates the need for human\-in\-the\-loop verification in high\-stakes deployments\. The environments and evaluation code are available under an open\-source license, enabling independent reproducibility verification\.

## Appendix FAdditional Results and Visual Diagnostics

The main visual diagnostics now appear next to the claims they support: collapse trajectories in Figure[4](https://arxiv.org/html/2606.31422#S6.F4), drift timing in Figure[5](https://arxiv.org/html/2606.31422#S6.F5), the ablation plot in Figure[6](https://arxiv.org/html/2606.31422#S6.F6), and the spatial frontier in Figure[7](https://arxiv.org/html/2606.31422#S7.F7)\. This appendix keeps the table\-level audits that are useful for reproducibility but would interrupt the main argument\.

### F\.1Useful\-Probe Rate Diagnostics

Table[5](https://arxiv.org/html/2606.31422#A6.T5)reports raw useful\-probe rate\. It supports the secondary metric discussion in Section[6\.2\.3](https://arxiv.org/html/2606.31422#S6.SS2.SSS3): EnvProbe\-Simple fires useful probes reliably on the spatial pool, while the ToolDAGWorld row is kept only as a scorer diagnostic because uninstantiated procedural fields distort the raw numerator\.

Table 5:Useful\-probe rate on the spatial pool\.UPR is the fraction of fired probes that correct an incorrect field\. ToolDAGWorld is shown only as a diagnostic row because its useful\-probe scorer is affected by uninstantiated procedural fields\.Table[6](https://arxiv.org/html/2606.31422#A6.T6)removes the selective\-trigger confound by normalizing useful probes by the available budget\. This is the more interpretable diagnostic for comparing policies that fire probes at different rates\.

Table 6:Budget\-normalized useful\-probe rate\.UPR~=\#​useful/B\\widetilde\{\\mathrm\{UPR\}\}=\\\#\\mathrm\{useful\}/Bnormalizes by the available probe budget, reducing the selective\-trigger confound that inflates raw UPR for policies that fire rarely\.
### F\.2Confident\-Wrong Estimator Audit

Table[7](https://arxiv.org/html/2606.31422#A6.T7)reports the estimators used to validate the confident\-wrong rate cited in Section[6\.2\.3](https://arxiv.org/html/2606.31422#S6.SS2.SSS3)\. The main text uses the canonical per\-belief estimator; the remaining rows are sanity checks that confirm the same failure mode under alternative scans\.

Table 7:pcwp\_\{\\mathrm\{cw\}\}estimator audit\.The canonical per\-belief estimator is used in the main text and Lemma[5\.5](https://arxiv.org/html/2606.31422#S5.Thmtheorem5); the remaining rows are robustness checks showing that the confident\-wrong rate stays above the0\.870\.87guardrail under alternative scans\.

## Appendix GAdditional Mechanism Details

##### Procedural action\-validity coupling\.

ToolDAGWorld has a sharper action\-validity boundary than the spatial environments: a single wrong belief about whether a prerequisite tool is loaded can invalidate the next API call before the aggregate world\-state accuracy falls below threshold\. This explains why procedural episodes sometimes show action collapse before measured drift, whereas spatial episodes more often show drift first\. The observed timing summary is:

##### Task\-weighted oracle\.

The unweighted oracle corrects the largest raw mismatch, but this is not always the field that matters for the next task action\. A task\-weighted oracle instead probesarg⁡maxi⁡wi​𝟏​\{bti≠gti\}\\arg\\max\_\{i\}w\_\{i\}\\mathbf\{1\}\\\{b\_\{t\}^\{i\}\\neq g\_\{t\}^\{i\}\\\}, aligning oracle behavior with the same weighted objective used inAHA\_\{H\}\. We use this oracle only as a diagnostic upper bound; it is not available to the agent\.

##### Uncertainty anti\-signal\.

The procedural ablation shows that verbalized uncertainty can push probes toward fields that are uncertain but not task\-critical\. Removinguiu\_\{i\}raisesAHA\_\{H\}but also drives the policy toward excessive belief checking, which is why task success falls\. The\(c\+d\)\(c\+d\)score preserves the useful structural signal while removing this self\-report failure mode\.