Belief-Calibrated Optimization: An Explicit World Model for Agentic Optimization

Summary (Overview)

• Core contribution: The paper introduces Belief-Calibrated Optimization (BCO), a method that maintains a persistent, in-context "world model" document that explicitly records and continuously revises the optimizer's beliefs about how the environment responds to scaffold edits.
• Key finding: BCO outperforms a matched control (vanilla) that lacks only the world model across five benchmarks spanning memory QA, tool-use QA, code-as-action app agents, and terminal agents, with train passrate improvements from +0.025 to +0.150 and held-out improvements from +0.022 to +0.152.
• Mechanism validation: An offline ablation demonstrates that the world model document carries reusable predictive information in its content—a fresh predictor given the intact document forecasts environmental responses more accurately than predictors given no document or a same-form scrambled copy.
• Transfer finding: After swapping the frozen target model, the BCO-selected scaffold leads on tested tasks, except where unbounded context consumption causes non-completions (notably on AppWorld).
• Theoretical grounding: The framework is positioned within the Bayes-Adaptive MDP setting, where the environment's response is unknown but fixed within a run, making the belief about that response the correct state to carry forward.

Introduction and Theoretical Foundation

LLM agent performance is jointly determined by model weights and the scaffold—the surrounding program that practitioners can modify. A recent paradigm uses coding-agent proposers as optimizers: they read current scores and traces, diagnose failures, and iteratively edit the scaffold source code. Each edit is informed by a belief about how the environment will respond—what went wrong and which change should help.

The Core Problem

The authors identify a critical deficiency in existing approaches: the belief remains implicit. It lives either in the proposer's reasoning on the current call or latent in its parameters, rather than being written down as a persistent artifact. Consequently, later optimization rounds see scores and traces but do not leverage the belief that produced previous edits, forcing the optimizer to reconstruct understanding from raw evidence each time.

Theoretical Foundation: Bayes-Adaptive MDP

The paper grounds its approach in the Bayes-Adaptive MDP framework. Within a single optimization run, three elements remain fixed:

• The frozen target model
• The scored task set $Q$
• The evaluation procedure

Since the environment's response is unknown but fixed, the correct state to carry forward between iterations is a belief about that response. The theoretical insight is that carrying a belief (rather than raw data) is the information-theoretically sound choice in this setting.

The Optimizer's Curse

The paper also formalizes the selection problem via the optimizer's-curse framework. The optimizer selects a candidate by:

$$\hat{x} = \underset{x \in \{x_1, \ldots, x_T\}}{\arg \max} \widehat{U}_Q(x), \qquad \widehat{U}_Q(x) = U(x) + \varepsilon_x, \tag{1}$$

where $U$ is the population utility and $\varepsilon_x$ collects split-specific and evaluation noise. Selecting on $\widehat{U}_Q$ while being judged on $U$ means the highest-scoring candidate on $Q$ is the one with the most favorable noise—so hill-climbing $\widehat{U}_Q$ alone can lose utility. An explicit environment model helps the proposer distinguish real effects from favorable noise.

Methodology

Overview of BCO

BCO maintains a persistent world model $W_t$—a single Markdown document (world_model_calibration.md)—that is copied into the proposer's workspace at the start of each iteration and written back at its end. The workflow follows a predict–observe–correct loop:

1. Predict: Before evaluation, the proposer records predictions for the candidate at task-subset granularity.
2. Observe: The candidate is executed to obtain scores and traces.
3. Correct: The proposer compares predicted vs. observed outcomes and updates the world model via a structured update operation.

Formally, the proposer's edit selection is:

$$a_t \sim \pi_{\text{opt}}(\cdot | h_t, W_t), \tag{2}$$

and the world model update is:

$$W_{t+1} = \text{Update}\left(W_t, \widehat{\mathcal{O}}_t, \mathcal{O}_t\right), \tag{3}$$

where $\widehat{\mathcal{O}}_t$ and $\mathcal{O}_t$ denote predicted and observed outcomes respectively. Including the prediction makes the update local—it specifies which beliefs were staked on the candidate and what outcomes they implied.

Belief Structure

The world model $W_t$ is a collection of atomic beliefs:

$$W_t = \{\beta_{t,i}\}_{i=1}^{m_t}, \quad \beta_{t,i} = (\phi_{t,i}, \mathcal{C}_{t,i}, c_{t,i}, s_{t,i}, E_{t,i}^{+}, E_{t,i}^{-}, \mu_{t,i}), \tag{4}$$

where:

• $\phi_{t,i}$: a falsifiable claim about execution or evaluation
• $\mathcal{C}_{t,i}$: conditions under which the claim applies
• $c_{t,i} \in [0,1]$: confidence level
• $s_{t,i} \in \{\text{hypothesis}, \text{confirmed}, \text{refuted}\}$: status
• $E_{t,i}^{+}$, $E_{t,i}^{-}$: supporting and contradictory evidence
• $\mu_{t,i}$: mass (approximate number of observed failures it explains)

BCO distinguishes two belief types:

• Execution beliefs: how edits affect agent behavior under specific conditions (model limitations, scaffold bottlenecks, task capabilities, external tool constraints)
• Evaluation beliefs: how reliably the evaluation system maps trajectories to outcomes (evaluator limitations, conditions where feedback is unreliable)

Belief Calibration

After evaluation, the proposer updates $W_t$ via a sequence of operations:

$$\Delta W_t = (\delta_1, \ldots, \delta_{k_t}), \quad \delta_j \in \{\texttt{Add}, \texttt{Revise}, \texttt{Merge}, \texttt{Remove}\}, \quad W_{t+1} = \texttt{Apply}(W_t, \Delta W_t). \tag{5}$$

• Add: inserts a new belief
• Revise: changes a belief's claim, scope, confidence, status, or evidence
• Merge: combines overlapping beliefs
• Remove: deletes refuted beliefs

The document starts empty—pre-seeding guessed failure modes is forbidden. A refuted belief remains on an append-only History record.

Implementation Details

• The proposer's instructions are assembled in a SKILL.md file; removing the calibration module yields the vanilla control.
• Both methods receive identical evidence: diffs, evaluation outputs, traces, source snapshots, and a cross-iteration task–score matrix.
• Predictions may name task IDs, but the source code may not branch on them—candidate code remains general.

Empirical Validation / Results

Experimental Setup

• Target models: DeepSeek-V4-Flash (memory, tool-use, code benchmarks), MiniMax-M3 (Terminal-Bench 2.0)
• Proposer: Kimi-K2.6/K2.7 (four benchmarks), Codex/GPT-5.6 (Terminal-Bench 2.0)
• Benchmarks:
  • Memory QA: LongMemEval-s (LME), LoCoMo
  • Tool-use QA: GAIA
  • Code-as-action: AppWorld
  • Terminal agents: Terminal-Bench 2.0 (TB2.0)

RQ1: Optimization and Held-Out Performance

Table 1: Held-out generalization across five benchmarks

BCO finishes higher than vanilla on both train and held-out across all five benchmarks. Held-out passrates are lower than train on every row (expected generalization gap), but the ordering is unchanged.

RQ2: Transfer to an Unseen Target Model

The selected artifacts were re-evaluated with gpt-5.6-luna (a different family/provider) at three reasoning-effort tiers (high/medium/low).

• GAIA: BCO has the highest passrate at all three effort levels. Notably, vanilla scored 0.111 below the initial scaffold at high effort—traces showed longer searches that overwrote earlier correct answers.
• AppWorld: Results diverge between full-set and completed-task analyses. The BCO scaffold's unbounded context re-injection exceeds the swapped target's context budget, causing non-completions on up to 99/372 tasks. Counting non-completions as failures, BCO is last at high/medium effort; restricting to tasks all three scaffolds complete, BCO is first at every tier (+0.007, +0.031, +0.091).

This reveals a trade-off: the BCO scaffold encodes a transferable task strategy, but its resource envelope (context consumption) is target-dependent.

RQ3: Does the World Model Carry Predictive Information?

A controlled offline ablation freezes candidates and outcomes, varying only the document given to a fresh predictor (who did not design the candidate):

• None: no document
• Scrambled: same length/format/vocabulary, but falsified mechanism verdicts and type-level effects
• Intact: the run's final world model with the candidate's outcome block removed

Table 2: Offline prediction ablation on 40 candidates

The ordering None < Scrambled < Intact holds on every measure. Scrambled over None suggests benefit from structure and naming regressions; Intact over Scrambled demonstrates additional information in the learned content. Both blind judges agree with the mechanical metrics. (Two-sided sign-test p = 0.125, with the run as the independent unit.)

Additional Ablation: Persistence Without Calibration

On LongMemEval-s, a third method (Notes) used a freely editable persistent file with no prediction, grading, or predict–observe–correct loop:

Table 3: Persistent-state ablation on LongMemEval-s

Persistence alone does not reproduce BCO's mean, though three short trajectories cannot conclusively show free-form notes are ineffective.

Theoretical and Practical Implications

Theoretical Contributions

1. Explicit world models for optimization: BCO formalizes what prior agentic optimization systems left implicit—the optimizer's belief about environment response. By grounding this in Bayes-Adaptive MDP theory, the paper provides a principled justification for what to carry between iterations: a belief, not raw data.

2. Falsifiability as a design principle: The belief structure (claim, conditions, confidence, status, evidence, mass) makes each belief individually testable and revisable. The predict–observe–correct loop creates a closed feedback cycle where predictions make beliefs locally addressable.

3. Content vs. form distinction: The ablation design (None vs. Scrambled vs. Intact) provides a rigorous methodology for isolating whether a persistent document's content (not just its structure) carries reusable information.

Practical Implications

1. Immediate performance gains: BCO delivers consistent improvements across diverse task families using only an in-context document—no model fine-tuning, no parametric surrogate, no learned solver required.

2. Transferable scaffolds: The selected scaffolds encode task strategies that transfer to unseen target models, suggesting the optimization discovers environment-general principles rather than target-specific hacks.

3. Context-budget awareness: The AppWorld transfer failure highlights that scaffolds must also optimize their resource envelope, not just passrate—a practical design constraint for real deployment.

4. Reproducibility and auditability: An explicit, falsifiable world model document is inspectable by humans, enabling better debugging and trust in automated optimization.

Conclusion

Belief-Calibrated Optimization makes the optimizer's knowledge of its environment explicit, falsifiable, and calibration-tracked. Across five benchmarks spanning four task families, BCO consistently outperforms a matched control lacking only the world model, on both train and held-out splits. The approach transfers to unseen target models on completed-task sets, and controlled ablations confirm the document's content carries reusable predictive information.

Key limitations acknowledged by the authors:

• The belief is an LLM's natural-language summary, not a statistically calibrated posterior
• The environment response is treated as fixed within a run; drift detection is not handled
• Each matched comparison contains one trajectory per method—evidence measures consistency across benchmarks rather than within-benchmark repetition

Future directions suggested: optimizing against multiple targets, scoring resource envelopes alongside passrates, and detecting response shifts to discount older evidence.