AgentCBO: Causal Belief Routing for Bayesian Optimization under Unknown Graphs
Organizations: Department of Computer Science, The University of Manchester, Manchester, UK · Alliance Manchester Business School, The University of Manchester, Manchester, UK
Abstract
Causal Bayesian optimization (CBO) typically relies on the unrealistic assumption of a perfectly known causal graph. Recent methods relax this constraint by coupling optimization with structure learning, but they often waste sample budgets on structural uncertainties that are irrelevant to the optimizer. In this paper, we formalize routing-equivalence to shift the objective from full causal-graph recovery to causal belief routing, where structural differences only matter when they alter optimizer-facing objects such as admissible exploration sets and do-priors. Furthermore, we propose agentcbo, a graph-belief routing framework that incorporates LLM causal priors through guarded proposal and commit mechanisms. Specifically, a Language-Prior Agent combines LLM beliefs with constraint-based discovery to extract a protected causal backbone alongside residual uncertain edges. A Calibration Agent and a Residual Repair Agent then refine only these uncertain structures through score-gated bounded local edits. Finally, a deterministic commit gate evaluates candidate updates using routing-proxy checks before allowing them to influence intervention selection. Across ten benchmarks, agentcbo performs comparably to known-graph CBO, demonstrating that guarded LLM priors can improve fixed-budget CBO performance.
Figures & tables
| Method | Structural scope | Evidence | Belief update | BO coupling |
|---|---|---|---|---|
| Dynamic PC-only | DAG | CI tests | Periodic | Guarded ESs and priors |
| CEO ( Branchini et al., 2023 ) | DAG posterior | Obs+int likelihood | Online | Entropy search |
| GACBO ( Mukherjee et al., 2024 ) | Plausible DAGs | Bayes scores + GP CS | Online | UCB over |
| CBO-U ( Durand et al., 2025 ) | Parents of | Parent-set CI | Online | Parent-aware surrogate |
| AgentCBO (ours) | Target-routed DAG | CI + LLM prior, guarded | Periodic, gated | Routing-aware ESs and priors |
| Reference | CBO baselines | LLM-assisted BO | AgentCBO variants | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Benchmark | BO | CBO | CEO | CBO-U | GACBO | LLAMBO | BORA | Prior | Calib | Full | ||||||||||
| CompleteGraph | ||||||||||||||||||||
| ToyGraph | ||||||||||||||||||||
| PSAGraph | ||||||||||||||||||||
| CCBOHealth | ||||||||||||||||||||
| HIVEpidemiology | ||||||||||||||||||||
| Executable-engine diagnostics | Semantic-robustness ablations | Component ablation | ||||||||||
| Benchmark | LP | CC | RA | LP-Anon | LP-Shuffled | Dynamic PC-only | ||||||
| CompleteGraph | ||||||||||||
| ToyGraph | ||||||||||||
| PSAGraph | ||||||||||||
| CCBOHealth | ||||||||||||
| HIVEpidemiology | ||||||||||||
Appendix figures & tables17 assets
Supplementary material from the paper’s appendix.
Appendix
| Benchmark | ES | Direction | Manipulative variables | Source | ||
|---|---|---|---|---|---|---|
| Chain-5 | 5 | 1 | 1 | min | synthetic.py:chain | |
| ToyGraph | 4 | 2 | 3 | min | toy_graph.py | |
| PSAGraph | 6 | 2 | 3 | min | psa_graph.py | |
| HIVEpidemiology | 5 | 1 | 1 | min | hiv_epidemiology.py | |
| CCBOHealth | 7 | 3 | 7 | min | Aspirin, Statin, Cancer-Inhibitor | ccbo_health.py |
| CompleteGraph | 7 | 3 | 7 | min | ; latent | complete_graph.py |
| ES-family assignment rule | Low-objective hits |
|---|---|
| Fixed | (70%) |
| Random pair-induced family per seed | (20%) |
| Fixed | |
| Fixed |
| Experiment | Configuration | Endpoint |
|---|---|---|
| Traced run | AgentCBO | |
| Matched-seed reference | AgentCBO-Prior | |
| Matched-seed reference | Native known-graph CBO | |
| Known-graph replay | Learned RuntimeES schedule ( ) | |
| Known-graph replay | Matched switch/cardinality ( ) | |
| Known-graph replay | Matched switch/cardinality ( ) |
| Benchmark | AgentCBO-Prior | Dynamic PC-only | , favors LP | ||
|---|---|---|---|---|---|
| CompleteGraph | |||||
| ToyGraph | |||||
| PSAGraph | |||||
| CCBOHealth | |||||
| HIVEpidemiology | |||||
| Chain-5 | |||||
| Comparator | Nominal | Wins / ties / losses | Holm | |
|---|---|---|---|---|
| BO | 0 | 0.0020 | 10 / 0 / 0 | 0.018 |
| GACBO | 0 | 0.0020 | 10 / 0 / 0 | 0.018 |
| CEO | 0 | 0.0078 | 8 / 2 / 0 | 0.055 |
| LLAMBO | 3 | 0.0098 | 9 / 0 / 1 | 0.059 |
| CBO-U | 5 | 0.0195 | 8 / 0 / 2 | 0.098 |
| BORA | 4 | 0.0273 | 8 / 1 / 1 | 0.109 |
| Benchmark | Unperturbed perturbed | Paired | Seeds worse |
|---|---|---|---|
| Rosenbrock | |||
| Ackley | |||
| PISHCATGraph | |||
| CCBOHealth | |||
| CompleteGraph |
| Paired contrast | Endpoint | 95% CI | |
|---|---|---|---|
| Corrupted-gated clean-gated | |||
| Corrupted-bypassed corrupted-gated |
| Coverage rescue | Prior | PC-only | Paired comparison |
|---|---|---|---|
| Inactive | 31 sets | 5 sets | 10/10 prior wins |
| mean | score | ||
| Active (default) | Tie | No measurable separation | |
| Nodes | Agent NG | PC NG | Known NG | 95% CI | Agent wins /10 | |
|---|---|---|---|---|---|---|
| 10 | 2 | |||||
| 20 | 3 | |||||
| 50 | 5 | |||||
| Optimization time (hours) | Largest family | |||||
|---|---|---|---|---|---|---|
| Nodes | Agent | PC | Known | Agent | PC | Known |
| 10 | ||||||
| 20 | ||||||
| 50 | ||||||
| Nodes | Prior time (seconds) | Prior tokens |
|---|---|---|
| 10 | 304 | 13,130 |
| 20 | 1,262 | 55,744 |
| 50 | 12,190 | 360,360 |
| AgentCBO-Prior | CC diagnostic | RA diagnostic | |
|---|---|---|---|
| LLM calls per run | |||
| LLM tokens per run | K | K | K |
| Discovery time, seconds | |||
| Relative LLM cost |
| Setting | CompleteGraph , min | PSAGraph , min | ||
|---|---|---|---|---|
| PC , stricter | ||||
| PC , default | ||||
| PC , looser | ||||
| LLM temperature | ||||
| LLM temperature , default | ||||
| LLM temperature | ||||
| Benchmark | Mean acceptance rate | Median # accepted rounds |
|---|---|---|
| CompleteGraph | 3 of 10 | |
| ToyGraph | 2 of 10 | |
| PSAGraph | 2 of 10 | |
| CCBOHealth | 2 of 10 | |
| HIVEpidemiology | 1 of 10 | |
| Chain-5 | 1 of 10 |
| Benchmark | (default) | |||||
|---|---|---|---|---|---|---|
| CompleteGraph | ||||||
| ToyGraph | ||||||
| PSAGraph | ||||||
| CCBOHealth | ||||||
| HIVEpidemiology | ||||||
| Chain-5 | ||||||
| Benchmark | Qwen3.5-35B | Qwen3.5-122B | Qwen3.5-397B | |||
|---|---|---|---|---|---|---|
| ToyGraph | ||||||
| Chain-5 | ||||||
| CompleteGraph | ||||||
| PSAGraph | ||||||
| Component and role | Input | Output | Activation | Authority |
|---|---|---|---|---|
| LP pairwise LLM Semantic prior elicitation | Variable pair, names, and domain context | Cause, effect, direction, confidence, and rationale | Prior elicitation | Supplies pairwise causal judgments |
| LP graph engine Observation-anchored graph construction | Pairwise judgments, observational data, and variables | Proposal DAG, frozen backbone, residual pairs, and confidence | Stack initialization and scheduled rediscovery | Constructs proposals through PC anchoring and guarded supplementation |
| Calibration Agent Statistical discovery configuration | LLM: sample and variable counts, names, approximate linearity and Gaussianity, and domain context. Pipeline: observations and LP state | LLM: algorithm/hyperparameter JSON. Pipeline: statistical challenger DAG | Calib/Full, after LP | Pipeline imports acyclic, score-improving residual edits while preserving the backbone |
| Residual Repair Agent Bounded local refinement | Current graph, PC adjacency, tool descriptions, state summary, and repair history. Observational evidence is accessible only through tools | Diagnostic actions and local-edit proposals | Full, after calibration | Pipeline imports at most five acyclic, score-improving residual edits while preserving the backbone |
| Commit Gate Graph replacement | Committed and candidate graphs, confidence, manipulators, and target | Retained or replacement graph | Periodic rediscovery | Applies confidence, manipulative-ancestry, and ancestor-subgraph nSHD checks |
| CBO runtime Route construction and intervention optimization | Committed graph, manipulators, target, observations, archived interventions, domains, and costs | RuntimeES, do-priors, selected interventions, and updated surrogates | Initialization, observe/intervene steps, and graph changes | Selects intervention sets and values by cost-normalized CEI |
Bayesian Optimization
Bayesian optimization uses probabilistic models and sequential experiments to find strong solutions when evaluating a black-box objective is costly.
See all 268 papers