Bayesian-Agent: Turning LLM Agent Skill Evolution from Guesswork into Posterior-Guided Decisions

Your agent's skill library keeps growing — but do you actually know how reliable each skill is? The IDEA Research team treats skills as Bayesian hypotheses, updating beliefs with verifier-confirmed results, so skill evolution shifts from "I think it works" to "the posterior tells me to explore, patch, split, compress, or retire."

1. The Problem: Why Do Agent Skill Libraries Get Messier Over Time?

A modern LLM agent is not just a model — it is a reasoning environment where prompts, tool interfaces, retrieval context, memory, SOPs, skills, and harness feedback jointly determine performance.

> "If a base model samples from P(X|θ), an agent samples from P(X|θ,C), where C contains the prompt, context, tools, memory, and harness feedback."

The core question: how should these external conditions (especially reusable skills and SOPs) be updated and maintained?

Three existing approaches all have flaws:

1. Heuristic reflection (e.g., Reflexion): the LLM reflects on failures and edits skills. But LLM reflection is itself noisy and can introduce erroneous edits that damage later tasks. 2. Raw counting (e.g., ExpeL, Voyager): treating observed successes/failures as reliable beliefs. But agent trajectories are sparse and non-i.i.d.; "3 successes" does not mean "75% reliability." 3. No systematic accumulation: many frameworks have no skill accumulation at all, restarting from zero each time.

Bayesian-Agent (arXiv:2606.08348), by Xiaojun Wu et al. from IDEA Research, HKUST (Guangzhou), and DataArcTech, makes the central move: treat skill evolution as a Bayesian optimization problem, not uncalibrated prompt accumulation.

2. The Framework: Skills Are Hypotheses, Verification Is Evidence

2.1 Formalization

With the LLM parameters frozen, the agent environment is decomposed into four modules:

• \(P_t\): prompts and skill text
• \(R_t\): retrieval / memory context
• \(A_t\): tool and action interfaces
• \(V_t\): verifiers or feedback channels

A reusable skill \(h_k\) is a hypothesis: can the model succeed given the prompt, context, and execution environment?

\[p_{k,t} = P(y_t = 1 \mid M_\theta, C_t, h_k, z_t)\]

where \(z_t = g(e_t)\) is a discrete feature vector extracted from the verified trajectory \(e_t\).

2.2 Trajectory Evidence Modeling

The framework only trusts real execution results from verifiers and assigns no confidence to LLM self-evaluations. Each trajectory records:

\[e_t = (x_t, h_k, c_t, y_t, u_t, \tau_t, \ell_t, r_t, m_t)\]

| Field | Meaning | |-----|------| | \(x_t\) | task input | | \(h_k\) | skill used | | \(c_t\) | task context | | \(y_t\) | verification result (0/1) | | \(u_t\) | total token cost | | \(\tau_t\) | number of turns | | \(\ell_t\) | elapsed time | | \(r_t\) | verifier-derived failure mode | | \(m_t\) | short scalar metadata |

Key design: trajectory signals are discretized into bucketed features (token count, turns, latency), balancing computational efficiency with information retention.

2.3 Categorical Bayesian Evidence Model

Laplace-smoothed prior (λ=1):

\[\pi_{k,t}(\ell) = \frac{N_{k,\ell} + \lambda}{\sum_{\ell' \in \mathcal{Y}} N_{k,\ell'} + \lambda|\mathcal{Y}|}\]

Factorized categorical likelihood score:

\[\tilde{p}_{k,t}(\ell|z) = \pi_{k,t}(\ell) \prod_{j=1}^{m} \theta_{k,j,t}^{(\ell)}(z_j)\]

Normalized success posterior:

\[s_{k,t}(z) = \frac{\tilde{p}_{k,t}(1|z)}{\tilde{p}_{k,t}(0|z) + \tilde{p}_{k,t}(1|z)}\]

A Beta-Bernoulli summary (α, β) is retained for compatibility, auditing, and conservative failure-dominance checks.

2.4 Versus Frequentist Counting

The paper sharply criticizes "counting as belief":

> "A frequency-style maintenance loop can count successes and failures after the fact, but sparse agent trajectories are rarely independent, identically distributed observations."

> "A single failure can be either a noisy accident or the first sign of a reusable failure mode."

The frequentist estimate:

\[\hat{p}_{k,t}(z) = \frac{\sum_{e_i} \mathbf{1}[y_i=1, g(e_i)=z]}{\sum_{e_i} \mathbf{1}[g(e_i)=z]}\]

Flaws: sparse evidence, context-dependence, expensive collection; a single failure might be noise or the first signal of a new failure mode.

The Bayesian approach uses frequency counts as evidence for updating posteriors, rather than treating counts themselves as beliefs.

3. Five Posterior-Guided Operations: From Probability to Action

The posterior is not just for viewing — it drives decisions:

\[\pi(B_k) = \begin{cases} E, & |D_k| = 0 \\ R, & \beta_k \geq 4, s_k(\emptyset) < 0.45 \\ P, & \max_r F_k(r) \geq 2 \\ S, & |C_k| \geq 3, |D_k| \geq 4 \\ C, & |D_k| \geq 3, s_k(\emptyset) \geq 0.72 \\ E, & \text{otherwise} \end{cases}\]

| Action | Symbol | Trigger | Meaning | |:---|:---|:---|:---| | Explore | E | no observations or uncertain posterior | collect more evidence, don't modify the skill | | Retire | R | β≥4 and success probability <0.45 | failure evidence dominates; skill unreliable | | Patch | P | same failure mode appears ≥2 times | convert repeated failure into a concrete guardrail | | Split | S | ≥3 contexts and ≥4 observations | one broad skill covering heterogeneous cases | | Compress | C | ≥3 observations and success probability ≥0.72 | keep reliable skills concise, prevent context overflow |

Conservative design: > "The policy is intentionally conservative: it should expose why a skill is being changed and avoid unnecessary textual drift."

3.1 A Real Case: Patch Evolution on SOP-Bench

Failure mode: left_expected_output_blank (leaving the output empty after writing)

Observation count: 3 → 4

Patch content: > "After writing, re-read test_set_with_outputs.csv and confirm the target row's expected_output is non-empty." > "If the target cell is empty, write the computed raw category string before finishing."

Stable guardrails (7 items, the 7th added by the patch): 1. Read sop.txt, tools.py, and the target CSV row 2. One-indexed rows (after header), update rows[row_index - 1] 3. Validate order_id, product_id, quantity_requested, customer_id, order_total 4. Compute only the target row, write only the expected_output cell 5. Use the Python csv module, preserving all rows/columns 6. Write the raw category string (e.g., manual_review), no XML/Markdown/quotes 7. Verify expected_output is non-empty before finishing

This is not vague advice — it is executable, precise rules.

4. Experiments: Three Benchmarks × Four Backends

4.1 Benchmarks

| Benchmark | Capability tested | Difficulty | |:---|:---|:---| | SOP-Bench | multi-step industrial SOP execution | medium | | Lifelong AgentBench | lifelong learning, cross-task experience reuse | medium-high | | RealFin-Bench | financial reasoning with implicit premises | high |

4.2 Core Results (deepseek-v4-flash)

| Benchmark | GA baseline | BA-Full | BA-Inc | Failures repaired | |:---|:---|:---|:---|:---| | SOP-Bench | 80% | 95% | 95% | 3/4 | | Lifelong AgentBench | 90% | 85% | 100% | 2/2 | | RealFin-Bench | 45% | 52% | 65% | 8/22 |

Key findings:

1. BA-Inc (incremental repair) is more stable than BA-Full (full online evolution): on Lifelong flash, BA-Full dropped from 90% to 85% — online evolution introduces ordering effects under sparse evidence. BA-Inc only repairs failed tasks, consuming just 12-15% of Full's tokens. 2. RealFin is the main battleground: 45% → 65% is the largest relative gain (+44%), but only 8 of 22 failures were repaired, showing that implicit-premise financial reasoning is hard to fully solve. 3. Token efficiency: SOP BA-Inc used 153k tokens (repair-only) vs. 1.39M for GA Full; efficiency improved 71% (19.63 vs 11.47).

4.3 Backend Ablation: Cross-Framework Validation

| Backend | SOP flash | Lifelong flash | RealFin flash | |:---|:---|:---|:---| | Native BA | 100% / 100% | 100% / 100% | 70% / 72.5% | | GenericAgent | 95% / 95% | 85% / 100% | 52.5% / 65% | | mini-swe-agent | 95% / 100% | 95% / 100% | 55% / 70% | | Claude Code | 100% / 100% | 100% / 100% | 80% / 87.5% |

*(Full / Inc)*

Claude Code + flash performed strongest on RealFin (80% → 87.5%), indicating interaction effects between framework and backend quality.

4.4 Negative Case: Why BA-Full Can Sometimes Hurt

Lifelong AgentBench + flash:

• GA: 90%
• BA-Full: 85% (↓5pp)
• BA-Inc: 100%

Cause: under sparse evidence, online evolution introduces ordering effects — modifying skills after early failures changes their usage order in later tasks. Incremental repair avoids this by only repairing failed tasks after the baseline run.

5. Comparison with Existing Methods

| Dimension | Reflexion / ExpeL / Voyager | Bayesian-Agent | |:---|:---|:---| | Update mechanism | LLM reflection, raw counts, heuristics | verified trajectories → Bayesian evidence → posterior actions | | Belief representation | text memory, count tables | feature-conditioned categorical posterior + Beta-Bernoulli | | Uncertainty | no explicit quantification | Laplace smoothing, posterior probabilities, conservative thresholds | | Auditability | black-box text accumulation | inspectable posterior audit trails, evolution snapshots | | Failure handling | one-shot repair or ignore | repeated failure modes → structured patches | | Skill quality | no explicit retirement | posterior <0.45 → retire |

The paper's core claim: > "Agent skill evolution should be evidence-calibrated, auditable, and explicit about uncertainty."

6. Limitations and Boundaries

Best suited for: repetitive tasks, availability of verifiers, repeated failure modes, injectable skill-text positions.

Not suited for: one-off tasks (no accumulation value), subjective labels (no verifier), highly non-stationary environments (posteriors go stale), failures caused by missing tools or data (not skill problems).

Technical limitations: the default is a factorized categorical model with Laplace smoothing, not full Bayesian structure learning; backend coverage is limited (4 agent frameworks); the Bayesian decision policy is conservative and could be made richer.

7. Conclusion: From "I Think It Works" to "The Posterior Tells Me"

Bayesian-Agent's core contribution is not making agents smarter, but making their skill accumulation more honest.

The framework: 1. Trusts only the verifier — no LLM self-evaluation 2. Uses feature-conditioned posteriors — not "3 successes" but "given context C, cost U, latency L, the posterior success probability is 0.72" 3. Decides conservatively — explore when evidence is insufficient, retire when failure dominates, patch on repeated failures, compress when reliable, split when too broad 4. Is auditable — every skill's posterior history, failure-mode counts, and patch evolution are preserved

This is not a more elaborate prompt-engineering framework but a cognitive architecture — upgrading the agent's skill library from an "experience pile" to a "probabilistic knowledge base."

Future directions:

• richer Bayesian decision policies beyond the default conservative one
• extension to more agent frameworks via posterior adapters
• sharing skill beliefs across models and deployments

When skill evolution shifts from gut feeling to probability, agent reliability finally has a mathematical foundation.

---

References

• Paper: Wu et al., "Bayesian-Agent: Posterior-Guided Skill Evolution for LLM Agent Harnesses", arXiv:2606.08348 (2026)
• Institutions: IDEA Research, HKUST (Guangzhou), DataArcTech Ltd.
• Code: open source (URL referenced in the paper)
• Models: deepseek-v4-flash / deepseek-v4-pro
• Benchmarks: SOP-Bench, Lifelong AgentBench, RealFin-Bench
• Backends: Native BA, GenericAgent, mini-swe-agent, Claude Code