Bayesian Control for Coding Agents Says Always Run the Tests Is Not a Strategy

“Always run the tests” is good advice for humans and a bad orchestration policy for agents. The human version assumes judgment: run the cheap checks while you work, pay for the expensive suite when the evidence justifies it, stop when another run will not teach you anything. Coding agents often get the bumper-sticker version: generate, test, retry, repeat until the budget catches fire.

Bayesian Control for Coding Agents is useful because it reframes that loop as a cost-sensitive decision problem. At each step, should the agent gather more evidence, refine the patch, call a critic, run the expensive verifier, regenerate, or stop? The answer should depend on a belief about whether the current candidate is correct and on the cost of buying more evidence. That sounds obvious. Most agent stacks still do not do it.

The controller in the paper maintains a posterior belief, written as b = P(Y=1 | evidence), over whether the current candidate will pass verification. The available actions include syntax critics, public-test critics, LLM critics, regeneration or refinement, oracle verification, and stopping. The system is evaluated with six LLM generators across nine coding benchmarks, including LiveCodeBench tiers, MBPP+, HumanEval+, SWE-Bench Lite and Verified, HumanEvalFix, and CodeContests.

The expensive part is deciding what evidence is worth buying

The paper compares Bayesian controllers against fixed policies: always verify, best-of-N, single-critic gates, and iterative refinement baselines. It models two cost regimes. In the “slow oracle, fast critics” setting, verification costs 90 units, syntax costs 1, public tests cost 2, LLM critics cost 5, and generation costs 10. In the “fast oracle, balanced critics” setting, verification costs 5, critics cost 1, and generation costs 10. Cost sweeps cover 54 benchmark-generator pairs.

The reported conclusion is not that Bayesian control magically dominates everything. It is better than that. The paper identifies three regimes. When verification is expensive and critics are noisy but useful, Bayesian controllers dominate by aggregating evidence before paying for the oracle. When public tests are close to oracle quality, public-test gates are often sufficient. When verification is cheap, simple always-verify policies work well.

That is exactly the kind of result operators should want. It does not ask teams to worship a technique. It says the right policy depends on your cost structure and signal quality. If your public tests predict production correctness well, use them aggressively. If your full verifier is cheap, run it. If your verifier is slow, expensive, or capacity-constrained, stop treating it like a reflex and start modeling whether the next call is worth it.

This maps cleanly to real coding-agent deployments. A syntax check is cheap. A unit test file might be cheap. A full integration suite, SWE-Bench-style container verifier, CI job, browser regression run, or frontier-model code review can be expensive in dollars, wall-clock time, queue slots, and developer patience. A policy that ignores those costs will either waste money or ship under-verified patches. Sometimes both, which is the least charming option.

Belief state beats retry folklore

The paper also treats the Bayesian belief state as an interpretable correctness score before final verification. On LCB-Medium/Hard with SAGE and gpt-oss-20b, it reports an average 0.866 PRR, ahead of sequence probability at 0.801, tool success rate at 0.795, and perplexity at 0.367. The exact ranking matters less than the direction: a calibrated belief over correctness is more useful for orchestration than vibes extracted from token probabilities or “the tool succeeded.”

This is where many agent products are still immature. They log tokens and maybe tool calls. They do not maintain a meaningful posterior over candidate correctness. They hard-code “retry three times,” “ask a judge,” or “run tests after every edit” and call it a workflow. That is not orchestration. That is a superstition with YAML.

A belief/cost layer gives teams better questions. How likely is this patch to pass? How much does a public test result change that likelihood? Is the LLM critic calibrated on this repo or just eloquent? At what threshold should we pay for full CI? When should the agent stop because the marginal value of another refinement is negative? When should it abstain and hand the task to a human because all cheap signals disagree?

The caveat is calibration. A posterior is not holy because someone wrote Bayes in the diagram. If the public-test critic is biased, if the LLM reviewer misses security regressions, if regeneration often breaks correct patches, or if the verifier itself is flaky, the controller can optimize the wrong thing with impressive confidence. The paper should be read as an architecture pattern, not a drop-in theorem.

For practitioners, the action item is direct: instrument the loop. Log every generated candidate, every critic call, every test run, every verifier result, every retry, every stop decision, and the cost of each action. Measure which signals actually predict correctness in your repositories. Calibrate critics against final outcomes. Track avoided verifier calls and also the painful category: expensive verifications skipped incorrectly. That is where the policy earns or loses trust.

This also belongs in budget controls. If you sell or operate coding agents, “maximum tokens per task” is too blunt. The budget governor should understand evidence. Spend more when critics disagree and the task is valuable. Spend less when a cheap verifier is decisive. Stop early when the candidate is clearly bad. Route uncertain high-impact patches to humans instead of asking the model to keep rolling dice with a different temperature.

The same idea applies beyond coding. Data agents, browser agents, research agents, and support agents all choose between cheap internal checks and expensive external actions. The mature version of agent orchestration will not be a fixed recipe. It will be a policy that buys evidence when evidence is worth more than it costs.

The editorial read: this paper is the control theory hiding under coding-agent economics. The next serious agents will not just generate patches. They will decide when confidence is high enough, when verification is worth paying for, and when another loop is just burning money to produce a more ornate failure.

Sources: arXiv, LiveCodeBench, SWE-bench, EvalPlus