Bayesian Control for Coding Agents¶
Conference: EMNLP 2026
Paper: https://aclanthology.org/2026.emnlp-main.1548/
Code: https://github.com/rvz16/bayesian_control_for_coding_agents
Area: LLM Reasoning
Keywords: coding agents, Bayesian control, POMDP, sequential hypothesis testing, uncertainty quantification
TL;DR¶
Formulating coding agent orchestration as a cost-sensitive Partially Observable Markov Decision Process (POMDP) enables dynamic Bayesian belief tracking of candidate correctness and value-of-information action selection, drastically reducing verification overhead while maximizing expected task utility.
Background & Motivation¶
Modern coding agent frameworks routinely wrap large language model generators with auxiliary tools, ranging from near-zero-cost syntax checkers and lightweight public test runners to LLM-based reviewers and expensive sandboxed execution verifiers. However, existing orchestration policies predominantly rely on rigid, hand-crafted heuristics, such as always verifying candidate patches, best-of-\(N\) sampling, fixed sequential pipelines, or unconstrained self-refinement loops. These static rules collapse multi-faceted decision spaces into arbitrary scalar thresholds or predetermined tool sequences, lacking any formal mechanism to maintain uncertainty over candidate correctness or weigh the marginal value of diagnostic evidence against its invocation cost.
The fundamental tension stems from the pronounced asymmetry between diagnostic tool costs and their reliability. Low-cost syntax checkers or unit test asserts provide noisy, incomplete feedback, whereas exhaustive hidden test suites or containerized verification harnesses provide ground-truth evaluation at substantial computational, financial, and latency costs. In environments where prior task difficulty varies widely and critics exhibit diverse failure modes, blindly triggering expensive verifiers squanders resources, while premature termination on false-negative diagnostic feedback permanently discards salvageable solutions. Existing frameworks cannot dynamically adjust decisions according to prior task difficulty, critic informativeness, generator repair likelihoods, or verification budgets.
This paper addresses this challenge by framing coding agent control as a formal Bayesian decision problem. Instead of retraining or fine-tuning the underlying frozen language models, all optimization is concentrated purely at the agentic control layer through cost-sensitive sequential hypothesis testing. Core idea: treat candidate correctness as a latent binary state, model critics as noisy diagnostic observations and generator iterations as stochastic transitions, and leverage the POMDP Bellman equation to actively decide whether to acquire more diagnostic evidence, refine the patch, trigger expensive verification, or terminate.
Method¶
Overall Architecture¶
The system models candidate program correctness as an unobserved binary state \(Y_t \in \{0, 1\}\), where \(Y_t = 1\) denotes that the current program \(c_t\) satisfies the oracle verification function \(O(c_t, x)\). At discrete time step \(t\), the controller maintains a posterior belief state \(b_t = P(Y_t = 1 \mid H_t)\) conditioned on interaction history \(H_t\). The available action space comprises code generation/refinement \(a_{\text{gen}}\) with cost \(C_{\text{gen}}\), \(k\) distinct critic tools \(a_{\text{crit}}^{(i)}\) with invocation cost \(C_{\text{crit}}^{(i)}\), and the terminal oracle verifier \(a_{\text{ver}}\) with cost \(C_{\text{ver}}\). The controller maximizes expected utility \(U(\pi) = \mathbb{E}_\pi [R \cdot Y_T - \sum_{t=1}^T C(a_t)]\) with task success reward normalized to \(R=100\).
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
In["Candidate Program $c_0$ & Specification $x$"] --> D1["Posterior Belief State Tracking & Bayesian Updating<br/>Prior $b_0$ & Likelihood-weighted Update $b_t$"]
D1 --> D2["Finite-Horizon Dynamic Programming Control<br/>Evaluate Expected Utility $Q_{\text{gen}}, Q_{\text{crit}}, Q_{\text{ver}}$"]
D2 -->|Acquire Evidence| Critic["Diagnostic Critic Inspection<br/>Syntax / Public Tests / LLM Judge"]
Critic -->|Return Observation $z_t$| D1
D2 -->|Refine Candidate| Gen["Generator Iterative Refinement<br/>Propagate via Transition Kernel $\hat{P}(\text{fix}), \hat{P}(\text{break})$"]
Gen -->|Emit Refined Patch $c_{t+1}$| D1
D2 -->|Terminal Commitment| Ver{"Oracle Verifier Evaluation<br/>Check Value-of-Information Threshold"}
Ver -->|Pass Verification| Success["Deliver Verified Code<br/>Realize Net Utility $R - \sum C$"]
Ver -->|Fail or Stop| Stop["Terminate Episode or Consume Retry"]
Key Designs¶
1. Posterior Belief State Tracking & Bayesian Updating: Addressing uncalibrated, noisy diagnostic signals from heterogeneous tool feedback In real-world software engineering pipelines, diagnostic tools exhibit vastly different informativeness and cost trade-offs. Syntax validation (\(a_{\text{crit}}^{\text{syn}}\)) is computationally negligible but offers near-zero discriminative signal on modern instruction-tuned LLMs; public test execution (\(a_{\text{crit}}^{\text{test}}\)) is moderately priced and highly predictive in competitive programming; LLM judges (\(a_{\text{crit}}^{\text{llm}}\)) provide semantic reasoning on diffs but incur noticeable API latency and false-positive rates. Rather than treating all tools uniformly, the controller pre-estimates conditional likelihoods \(\hat{P}_i(z = \text{pass} \mid Y = y)\) on a disjoint 75% calibration split using Beta(1, 1) smoothing. Upon receiving binary observation \(z \in \{\text{pass}, \text{fail}\}\) from critic \(i\), the belief updates via Bayes' rule: $\(b_{t+1} = \frac{P_i(z \mid Y_t = 1) b_t}{P_i(z \mid Y_t = 1) b_t + P_i(z \mid Y_t = 0)(1 - b_t)}\)$ The update magnitude is proportional to the critic informativeness gap \(\gamma_i = P_i(z=\text{pass} \mid Y=1) - P_i(z=\text{pass} \mid Y=0)\). Uninformative tools (\(\gamma_i \approx 0\)) leave the belief virtually untouched, while highly informative critics rapidly shift \(b_t\) across decision boundaries, naturally weighting evidence and preventing error propagation common in brittle heuristic pipelines.
2. Finite-Horizon Dynamic Programming Control: Overcoming greedy myopic limitations in valuing multi-step repair trajectories A standard one-step greedy policy (bayesian_greedy) resets its belief to the task prior \(b_0\) upon regeneration, assuming fresh independent sampling and thus failing to recognize that iterative refinement on broken code can compound into high-probability successes. To unlock multi-turn credit assignment, the finite-horizon dynamic programming controller (bayesian_DP) estimates empirical transition kernel probabilities from iterative refinement corpora: fix probability \(\hat{p}_{01} = P(Y_{t+1}=1 \mid Y_t=0)\) and break probability \(\hat{p}_{10} = P(Y_{t+1}=0 \mid Y_t=1)\). Refinement propagates belief as \(b_{t+1} = b_t(1 - \hat{p}_{10}) + (1 - b_t)\hat{p}_{01}\). The controller discretizes the belief interval \([0, 1]\) into a uniform 51-point grid and solves the backward Bellman recursion over planning horizon \(H=3\): $\(V(b_t) = \max \left\{ Q_{\text{gen}}(b_t),\, \max_i Q_{\text{crit}}^{(i)}(b_t),\, Q_{\text{ver}}(b_t),\, Q_{\text{stop}}(b_t) \right\}\)$ where \(Q_{\text{ver}}(b_t) = b_t R - C_{\text{ver}}\) and \(Q_{\text{crit}}^{(i)}(b_t) = \mathbb{E}_{z}[V(b_{t+1}) \mid b_t, a_{\text{crit}}^{(i)}] - C_{\text{crit}}^{(i)}\). By precomputing optimal action lookup tables offline, bayesian_DP executes online decisions in \(O(1)\) time while correctly valuing multi-step critic-refine-verify trajectories.
Benchmark & Evaluation Protocol¶
The framework is evaluated across six diverse generator LLMs (gpt-5-mini, claude-haiku-4.5, claude-sonnet-4.5, qwen3-coder, Qwen2.5-Coder-32B-Instruct, and gpt-oss-20b) over nine benchmarks across three core tasks: function-level synthesis (LCB-easy/medium/hard, MBPP+, HumanEval+), repository-level patch generation (SWE-Bench Lite, SWE-Bench Verified), and bug-fixing (HumanEvalFix, CodeContests). Experiments evaluate two representative cost regimes: "slow oracle, fast critics" (\(C_{\text{ver}}=90, C_{\text{syn}}=1, C_{\text{test}}=2, C_{\text{llm}}=5, C_{\text{gen}}=10, R=100\), matching heavy containerized test suites) and "fast oracle, balanced critics" (\(C_{\text{ver}}=5, C_{\text{crit}}=1, C_{\text{gen}}=10, R=100\), matching unit-test loops). The primary evaluation metric is the per-instance utility gap \(\Delta_\pi = \bar{U}_\pi - \bar{U}_{\text{always\_verify}}\), supported by paired-bootstrap 95% confidence intervals.
Key Experimental Results¶
Main Results: Multi-Benchmark Cost-Adjusted Utility¶
The table below extracts representative results from Table 7 in the paper under the slow-oracle, fast-critics regime, reporting the utility gap \(\Delta_\pi\) relative to always_verify (positive values denote superior cost-adjusted performance over blind verification):
| Benchmark | Generator | Best-of-3 | gate(Cr_test) | Fixed-Pipeline | Self-Refine | Reflexion | Bayesian Greedy | Bayes-DP (Ours) |
|---|---|---|---|---|---|---|---|---|
| LCB-hard | claude-haiku-4.5 | -20.0 | -12.8 | -12.1 | -25.6 | -15.4 | +2.8 | +2.1 |
| LCB-hard | gpt-5-mini | -20.0 | +4.3 | -7.5 | -33.2 | -4.4 | +0.3 | +2.4 |
| LCB-medium | claude-haiku-4.5 | -18.1 | -11.8 | -8.3 | -15.0 | -23.2 | -16.9 | +2.6 |
| LCB-medium | gpt-5-mini | -24.0 | -1.1 | -3.0 | -34.4 | -17.0 | +0.7 | +1.7 |
| SWE-Bench Lite | claude-haiku-4.5 | -20.0 | – | +29.3 | -57.7 | -136.0 | +67.3 | +67.6 |
| SWE-Bench Lite | gpt-5-mini | -17.3 | – | +13.7 | -24.4 | -102.7 | +62.0 | +62.0 |
| SWE-Bench Verified | claude-haiku-4.5 | -16.0 | – | +5.0 | -42.6 | -116.0 | +56.0 | +56.0 |
| SWE-Bench Verified | gpt-5-mini | -12.0 | – | +32.3 | -52.0 | -256.0 | +74.0 | +74.0 |
| CodeContests | claude-haiku-4.5 | -41.4 | -9.9 | -13.5 | -40.0 | -15.1 | -16.2 | +2.7 |
| CodeContests | gpt-5-mini | -22.5 | -1.9 | -6.8 | -27.5 | -103.9 | -13.5 | +2.0 |
(Note: SWE-Bench lacks a public-test split distinct from the oracle verifier, marked as "–". Bold numbers indicate per-cell winners.)
Ablation Study: Comparison with LLM-Driven Agents & Uncertainty Quantification¶
Under a unified setup with Claude Haiku 4.5 across five benchmarks (HumanEval+, HumanEvalFix, MBPP+, LCB-Medium, LCB-Hard, Table 11 in Appendix C.2), Bayes-DP demonstrates substantial efficiency and cost-adjusted utility advantages:
| Agent Framework | pass@1 (%) | Cost ($/task) | Wall-clock (s) | Verifier Calls | Cost-adjusted Utility U(π) |
|---|---|---|---|---|---|
| Bayes-DP (Ours) | 57.3% | 0.0036 | 6.5s | 1.09 | +39.4 |
| Reflexion | 64.0% | 0.0116 | 16.1s | 2.15 | +20.3 |
| Self-Refine | 57.3% | 0.0132 | 16.4s | 0.00 | +8.3 |
| LangChain-ReAct | 78.7% | 0.0388 | 30.1s | 1.57 | +0.4 |
| AutoGen | 74.0% | 0.0590 | 38.7s | 1.51 | -26.2 |
| smolagents | 76.7% | 0.0884 | 41.0s | 1.71 | -31.8 |
In post-hoc uncertainty quantification evaluated via Prediction Rejection Ratio ([email protected], Table 1 in main text): - Perplexity baseline achieves an average PRR of 0.140; - Sequence Probability achieves 0.379; - Verbalized Confidence achieves 0.303; - Tool Success Rate achieves 0.428; - Bayes State (Ours) achieves 0.442 (reaching 0.849 on CodeContests); - Bayes State + UQ (Ours) achieves the top score of 0.512.
Key Findings¶
- Three Dominant Control Regimes: Pooling 7,020 evaluation sweep points across 54 generator-benchmark pairs establishes clear operational regions:
- Regime A (Bayesian dominance, \(C_{\text{ver}}/R \gtrsim 1\)): When verification is expensive and critics are informative but imperfect, Bayesian policies dramatically outperform all baselines (e.g., +56 to +74 utility gains on SWE-Bench), accurately filtering false candidates.
- Regime B (Public-test gate dominance, \(10^{-1} \lesssim C_{\text{ver}}/R \lesssim 1\)): When public tests are highly predictive of hidden tests (\(\gamma_{\text{test}} \ge 0.7\)), single-critic gating matches or marginally beats Bayesian aggregation by avoiding inference overhead.
- Regime C (Unconditional verification dominance, \(C_{\text{ver}}/R \lesssim 10^{-1}\) or high prior): When verification is cheap or initial candidate accuracy is saturated (\(\ge 85\%\)), the cost of running intermediate critics exceeds verification, making always_verify optimal.
- Dynamic Programming Value Boundary: Bayes-DP strictly outperforms Bayesian greedy when the empirical repair probability \(\hat{P}(\text{fix} \mid \text{broken}) \ge 0.15\). When repair transitions are negligible, Bayes-DP naturally collapses to the greedy boundary without degraded utility.
- Superior Pareto Efficiency: Compared with ReAct or multi-agent architectures that achieve higher raw pass@1 at 3-25x higher financial and latency costs, Bayes-DP attains the highest net utility, firmly establishing the Pareto frontier.
Highlights & Insights¶
- Economic Value-of-Information Formulation: Formulating tool calls as explicit information purchases rooted in decision theory replaces ad-hoc prompt chaining with rigorous mathematical foundations, providing formal convergence guarantees and clean resource-allocation mechanics.
- Negligible Computational Overhead: Because Bellman value functions are solved offline over a 51-point grid, online decision-making requires only \(O(1)\) table lookups, introducing less than 0.0001%–0.4% overhead relative to generation and execution times.
- Dual Functionality as Decision State and Uncertainty Metric: The posterior belief state not only drives execution decisions during code synthesis but also excels as a calibrated post-hoc uncertainty score that substantially outperforms raw sequence probabilities and verbalized confidence scores.
Limitations & Future Work¶
- Python-Centric Benchmarking: Evaluations primarily encompass Python codebases. While the underlying POMDP mathematics are language-agnostic, cross-language tool likelihood calibration and multi-file AST parsing warrant broader empirical study.
- Static Likelihood Calibration: Transition kernels and critic likelihoods are estimated on held-out calibration splits under the assumption of stationary problem distributions; distribution shifts in real-world proprietary repositories could degrade belief accuracy.
- Future Directions: Extending the framework to online non-stationary Bayesian updates (e.g., updating critic confusion matrices on-the-fly) and expanding Bayesian control to multi-agent software engineering workflows beyond code synthesis.
Related Work & Insights¶
- vs Self-Refine / Reflexion: Iterative self-critique baselines operate without principled stopping criteria, leading to runaway API costs or regressive code editing; Bayesian control regulates refinement dynamically, cutting cost by ~60% while doubling net utility.
- vs LangChain-ReAct / AutoGen / smolagents: LLM-driven agentic loops delegate action routing to expensive generative tokens; Bayes-DP handles orchestration via lightweight decision theory, yielding superior cost-adjusted returns.
- vs Static Confidence Thresholds: Fixed confidence cutoffs treat initial uncertainty and post-critique uncertainty identically; the Bayesian POMDP framework dynamically incorporates action-specific likelihoods and remaining budgets.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ Elegant and principled formulation of coding agent orchestration as a cost-sensitive POMDP sequential hypothesis test.
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive evaluation across 6 models, 9 benchmarks, 7,020 sweep points, and rigorous statistical tests.
- Writing Quality: ⭐⭐⭐⭐⭐ Exceptionally clear narrative, disciplined mathematical exposition, and high-density, informative visualizations.
- Value: ⭐⭐⭐⭐⭐ Directly addresses the pressing industry bottlenecks of agentic compute cost, latency explosion, and orchestration reliability.