Source-linked AI summary
Belief-Calibrated Optimization: An Explicit World Model for Agentic Optimization
Yuhan Chen, Zhihua Tian, Mahavir Dabas, Charith Peris, Rahul Gupta, Ming Jin, Feiyang Kang, Siyuan Zhang, Nan Wang, Ruoxi Jia
TL;DR
LLM-agent optimization usually leaves the beliefs guiding scaffold edits implicit, limiting their reuse across rounds. BCO makes those beliefs a persistent, revisable world model within the optimization loop. It outperforms a matched control across five benchmarks and held-out splits, transfers favorably after target-model swaps except under context overruns, and its content improves offline outcome prediction.
Problem
Optimization rounds observe scores and traces but typically do not retain the beliefs that explain failures or motivate edits.
Method
BCO writes beliefs about environmental responses into a persistent in-context world model and revises them from predicted-versus-observed candidate outcomes.
Results
BCO reaches higher train passrate than vanilla on all five benchmarks and preserves the gap on every held-out split.
Takeaways & Limitations
The accumulated world model contains reusable content: a fresh predictor forecasts environmental responses more accurately when given it.
Takeaways & Limitations
The protocol treats the environment’s response as fixed within a run and does not detect shifts requiring older evidence to be discounted.
Abstract
from arXiv · showhide
The performance of an LLM agent depends on the scaffold around a frozen model. A common way to improve that scaffold is to use a coding agent as an optimizer: it reads current scores and traces and iteratively edits the source, producing a new candidate each round. Each edit is chosen according to a belief about how the environment will respond: what went wrong, and which change should help. That belief is typically implicit. It lives in the coding agent's reasoning on the current call, or remains latent in its parameters, rather than as something written down. Later calls therefore see scores and traces, but they do not use that belief. We introduce Belief-Calibrated Optimization (BCO), a method that writes that belief down as a persistent in-context document and continually revises that document as new candidates are evaluated. The resulting document is a world model: the current account of how the environment responds to edits. Added to an otherwise standard loop, BCO reaches a higher train passrate than a matched control that lacks only the world model, on five benchmarks spanning memory QA, tool-use QA, code-as-action app agents, and terminal agents. The gap remains on every held-out split, which is not used to select the candidate. After a target-model swap, in which the frozen model is replaced and the scaffold is not, the selected BCO scaffold leads on the tasks we test, except where context-window overruns leave it unfinished. An offline ablation then asks whether that gap comes from what the world model says. A fresh predictor given the accumulated document forecasts how the environment will respond more accurately than predictors given either no document or a same-form copy whose content has been falsified. The comparison indicates that the document carries reusable information in its content, not only in its form.
1 Introduction
Agentic optimization improves a frozen model by editing its surrounding scaffold, but the belief guiding each edit is usually implicit and unavailable to later rounds. BCO makes that belief persistent and revisable as a world model, with reported gains across benchmarks and held-out splits.
- Only the scaffold evolves while the underlying LLM remains frozen.
- Implicit beliefs about bottlenecks and helpful edits are not reused by later optimization rounds.
- BCO records the optimizer’s belief in a persistent in-context world model and revises it as candidates are evaluated.
- Across five benchmarks, BCO outperforms a matched control lacking only the world model on train passrate and every held-out split.
2 Iterative Agentic Optimization
Agentic optimization iteratively proposes artifact edits, evaluates them on a fixed task set, and uses observed evidence to guide later proposals. Because evaluation scores contain noise, optimizing them alone can select candidates whose apparent gains do not reflect population utility.
- Agentic optimization improves an artifact through proposed modifications, outcome evaluation, and evidence-guided subsequent proposals.
- At each iteration, the proposer edits a previously evaluated artifact and receives aggregate scores, task results, traces, and tool outputs.
- The environment evaluates candidates on a fixed scored task set drawn once from a task distribution.
- Because observed scores combine population utility with evaluation noise, hill-climbing the scored estimate alone can lose utility on the task distribution.
3 Belief-Calibrated Optimization
BCO augments the standard propose-and-evaluate loop with a persistent world model that predicts candidate effects, compares them with observations, and updates explicit beliefs. Its implementation stores falsifiable, conditional beliefs with confidence and evidence, then uses calibrated revisions to guide later edits.
- 3.1 Overview: BCO carries a persistent belief about the environment’s fixed response while choosing edits from interaction history and the current world model.
- 3.1 Overview: Before evaluation, BCO predicts task-level effects; afterward, it compares predictions with scores and traces to update the world model.
- 3.1 Overview: Prediction discrepancies localize which beliefs were implicated, making updates more targeted than merely signaling that revision is needed.
- Instantiation: The world model is a Markdown document copied into and written back from the proposer’s workspace each iteration, while vanilla removes the calibration module.
- 3.2 Belief Construction: Each atomic belief records a falsifiable claim, applicability conditions, confidence, status, supporting and contradictory evidence, and explanatory mass.
- 3.3 Belief Calibration: Calibration updates beliefs individually by adding, revising, merging, or removing them, while unaffected beliefs remain unchanged.
4 Experiments
The experiments compare BCO with a matched vanilla protocol across five benchmarks, evaluate transfer to an unseen target model, and test whether the world model contains reusable predictive information. BCO improves train and held-out passrates broadly, but context consumption constrains transfer in AppWorld.
- Experimental design: The matched comparison holds the initial scaffold, editable source, target, splits, harness, proposer, and iteration budget constant while adding only the calibration layer.
- RQ1: Optimization and generalization: BCO ends higher than vanilla on train passrate on every benchmark, with gains from +0.025 on TB2.0 to +0.150 on GAIA.
- RQ1: Optimization and generalization: BCO remains higher on held-out passrate on every benchmark, with gains from +0.022 on TB2.0 to +0.152 on GAIA.Held-out passrate is lower than train passrate on every row.
- RQ2: Target-model transfer: After swapping to gpt-5.6-luna, BCO has the highest GAIA passrate at high, medium, and low reasoning effort.All three scaffolds complete every GAIA task.
- RQ2: Target-model transfer: On AppWorld, BCO ranks first at every reasoning tier among tasks completed by all three scaffolds, but context overruns reduce its full-set scores.It returns no output on 99/77/65 of 372 tasks at high/medium/low effort, making it last at high and medium effort when non-completions count as failures.
- RQ3: World-model information: The offline ablation orders predictors as None < Scrambled < Intact on every measure, indicating reusable information in the world model’s learned content.Candidates are nested within four runs, and the run-level sign test is p = 0.125.
- Additional ablation: Persistence without calibration yields means 0.430 for vanilla, 0.427 for Notes, and 0.467 for BCO on LongMemEval-s training trajectories.The comparison uses three independent ten-iteration trajectories on 100 training examples.
5 Related Work
Related work studies scaffold optimization, verbal reflection and memory, and Bayesian views of sequential decision-making. BCO differs by maintaining an explicit natural-language belief about edit responses rather than only episodic memory or a parametric surrogate.
- LLM-driven optimization of frozen-model programs: Prior work optimizes agent harnesses, supports composable or evolvable systems, and studies sustained self-improvement and scaffold rewriting.
- Verbal self-reflection and memory: Other approaches retain experience through self-feedback, tool-verified correction, persistent skill libraries, or streamed memory.
- POMDPs, Bayes-adaptive RL, and Bayesian optimization: The paper frames optimization as a Bayes-Adaptive MDP in which the environment response is unknown but fixed within a run, so the carried state is a belief about that response.
- POMDPs, Bayes-adaptive RL, and Bayesian optimization: BCO instantiates world-model and acquisition-like roles in natural language and context without a parametric surrogate or learned solver.
6 Conclusion
The conclusion presents BCO as explicit, revisable optimization knowledge that improves scaffold search and can transfer across target models. It also identifies context use as a practical boundary and reports evidence that the world model’s content is reusable.
- BCO writes the optimizer’s belief about edit responses into a persistent world model and revises it through predict–observe–correct.
- Across five benchmarks, BCO achieves higher train passrate than vanilla and preserves the gap on every held-out split.
- After target replacement, BCO ranks first across all GAIA settings and common completed-task AppWorld sets, while unbounded context use lowers full-set AppWorld performance.
- A fresh predictor forecasts candidate outcomes more accurately with the accumulated world model, indicating that its document contains information usable beyond the originating run.
7 Limitations •
The paper’s limitations concern approximate belief quality, an unknown-but-fixed environment assumption, target-dependent resource use, and the scope of the evaluation.
- Belief quality: The world model is an LLM-generated natural-language summary rather than a statistically calibrated posterior, and its self-assessment is heuristic.
- Environment stability: The protocol assumes the target model, benchmark, and evaluation procedure remain fixed within a run, so target or tool drift is not handled.
- Environment stability: A target swap or external-tool drift would require detecting the changed response and discounting older evidence, which the current protocol does not include.
- Transfer and resource use: AppWorld transfer shows that target-dependent resource use can affect full-set performance, motivating future optimization of a candidate’s resource envelope alongside passrate.
- Evaluation scope: The evaluation covers five screened benchmarks, with four sharing one proposer family and target model while Terminal-Bench 2.0 uses an independent stack.
B.2 The world model
The world model records explicit, reusable beliefs about how edits affect the environment and updates them using evidence from evaluated candidates. Its protocol preserves refuted claims, rejects unsupported credit, and uses predictions to guide targeted scaffold revisions.
- World-model representation: Each belief records a claim, confidence, status, supporting and contradictory evidence, and explanatory mass.The mass approximates the number of observed failures explained by the belief and helps prioritize experimental budget.
- Evidence and calibration: The world model treats repeated normalized failures as stronger stagnation evidence than plan wording when the solver continues modifying parameters.This makes external failure output a basis for updating beliefs about persistent bottlenecks.
- World-model representation: Refuted beliefs remain recorded so the same direction is not proposed again.The protocol also refuses to credit score movement when the candidate leaves no corresponding trace signature.
- Predict–observe–correct: The model predicted that compressed evidence summaries would improve a long-context subset, then revised the scaffold after observing regressions caused by unconditional summarization.The revision gated summarization on empty or placeholder answers and accepted only concrete outputs.
- Predict–observe–correct: Five additional tasks passed, zero previously passing tasks regressed, and train passrate rose from 0.450 to 0.575.The grading record attributes the improvement to the iteration-16 refinement while excluding unstable multi-run episodes from the stable signal.
- Evidence and calibration: The prediction-and-grading procedure compares forecasts with mechanically computed task-type gains and regressions using fresh sandboxed judges focused on accuracy.Judges see anonymized predictions and ground-truth deltas, without repeats or self-consistency voting.
C Initial-Scaffold Stability and Excluded Optimization Diagnostics
The diagnostic analysis exposes instability and selection caveats in the optimization evidence. Memory results use best-of-three held-out selection, while Spider2-lite and the original Terminal-Bench split were excluded from the main comparison for methodological reasons.
- Memory-benchmark selection: Memory rows use the best held-out score among each method’s three highest-train candidates, so the reported values are best-of-three selections.The eligible held-out spread was 0.5925–0.6075 for bco versus 0.4825–0.5325 for vanilla on LongMemEval-s, and 0.4451–0.4534 versus 0.3437–0.3754 on LoCoMo.
- Memory-benchmark selection: Two below-threshold candidates were evaluated but excluded because using them would abandon the train-threshold eligibility rule.The excluded candidates had the highest outside-eligible held-out scores for their respective benchmarks.
- Excluded diagnostics: Spider2-lite initial-scaffold repeats produced aggregate passrates of 0.577, 0.519, 0.558, and 0.462.Across repeats, 45 of 104 tasks received both a pass and a fail, weakening attribution of observed changes to edits.
- Excluded diagnostics: Because Spider2-lite method ordering changed across campaigns, it was not included among the five main benchmarks or summarized with a single winner.These exploratory runs also did not define the main Terminal-Bench split.
- Terminal-Bench split: The main Terminal-Bench comparison uses a stability-screened 20-task training subset rather than the initial uncurated split.The initial split was dominated by unstable and timeout-bound tasks, with held-out scores of 0.470 initially, 0.463 for bco, and 0.455 for vanilla.
D Full Target-Swap Results
Full target-swap evaluation compares completed tasks across all methods and also restricts analysis to their common completed set. Context-window overruns can therefore appear as failures in the full analysis and remove many AppWorld cases from common-set comparisons.
- Completion handling: “All” counts context-window overruns as failures, whereas “common” includes only tasks completed by all three scaffolds.GAIA has no differential completion, so its two analyses coincide.
- Completion handling: On AppWorld, the common-set restriction excludes 99, 77, and 65 bco non-completions at high, medium, and low effort, respectively.The restriction changes the comparison population by removing bco cases that did not complete.
E Proposer Token Cost
BCO’s token cost reflects a read–write trade rather than uniformly higher prompting overhead. It saves raw-trace reads, but total tokens fall mainly when benchmark evidence induces heavy history re-reading.
- Read–write trade: Raw-trace reads fall 20–69% with bco, while each iteration writes the updated belief and prediction.The compact append-only belief reduces repeated derivation from bulky history, but adds writing overhead.
- Benchmark split: Total proposer tokens fall on memory QA and GAIA but reach or exceed parity on AppWorld and Terminal-Bench 2.0.Matched-pair changes are −27.4% for LongMemEval-s, −24.7% for LoCoMo, −12.4% for GAIA, +5.2% for AppWorld, and +26.2% for Terminal-Bench 2.0.
- Benchmark split: The benchmark split tracks evidence shape rather than optimization horizon: truncating longer runs at iteration 10 already reproduces the memory and GAIA savings.The iteration-10 differences are −37.1% for LongMemEval-s, −24.4% for LoCoMo, and −10.0% for GAIA.
- Benchmark split: On agentic environments, a few bulky trajectories leave little redundant reading for bco to replace, so its added writing can dominate.This explains why AppWorld and Terminal-Bench 2.0 are at or above parity despite lower raw-trace reads.
- Persistent-memory diagnostic: The persistent-memory diagnostic is noisy: bco’s mean training passrate is 0.467 versus 0.430 for vanilla and 0.427 for Notes.Within-method dispersion exceeds both mean gaps, so three ten-iteration trajectories do not establish reliable superiority over free-form persistent memory.
G Per-Run Breakdown of the Offline Ablation
The offline ablation’s evidence is consistent across runs and judges, while online prediction scores are confounded by changing outcome base rates and protocol-driven optimism. The per-run diagnostic therefore supports content-sensitive belief evaluation more than online score trends.
- Per-run judge breakdown: All twelve run-level comparisons favor the same condition under both judges, although four runs cannot yield a sign-test p-value below 0.125.The authors interpret this as replication across runs and judges rather than a small-p-value result.
- Metric choice: Downside precision is used because recall rewards naming many regressions and is undefined for a batch without any realized-regressed type.Precision remains defined for all 40 paired candidates.
- Concrete prediction: In a LongMemEval-s example, Intact correctly predicts a regression of −0.09 for single-session-assistant, while None predicts that single-session-preference will hurt despite a +0.25 improvement.The blind judge selects Intact; the example illustrates downside precision rather than providing independent evidence.
- Online-score limitation: The online prediction score cannot diagnose belief quality because the protocol requires a positive improvement bet every iteration.The predicted net-bet midpoint is positive in 60/60 logged iterations.
- Online-score limitation: Upside hit rates decline as the positive class shrinks near the performance ceiling, even when predictor skill may remain stable.Realized-improved types fall from 0.389 to 0.267 on LongMemEval-s and from 0.200 to 0.083 on LoCoMo; base-rate adjustment makes the decline smaller.
- Cost context: The token-cost curves separate early on memory benchmarks but nearly coincide on AppWorld and rise above vanilla mid-run on Terminal-Bench 2.0.This visual pattern matches the broader evidence-shape account of proposer token use.