💬 NLP

Bayesian-Agent: Posterior-Guided Skill Evolution for LLM Agent Harnesses

The paper introduces Bayesian-Agent, a framework that treats reusable skills and SOPs as probabilistic hypotheses to guide their evolution through posterior-guided harness optimization, significantly improving LLM agent performance on benchmarks like SOP-Bench and Lifelong AgentBench without modifying model weights.

Original authors: Xiaojun Wu, Cehao Yang, Honghao Liu, Xueyuan Lin, Wenjie Zhang, Zhichao Shi, Xuhui Jiang, Chengjin Xu, Jia Li, Jian Guo

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiaojun Wu, Cehao Yang, Honghao Liu, Xueyuan Lin, Wenjie Zhang, Zhichao Shi, Xuhui Jiang, Chengjin Xu, Jia Li, Jian Guo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but slightly stubborn, robot assistant. This assistant is great at thinking, but it doesn't learn from its mistakes the way a human does. If you ask it to bake a cake and it burns the first one, it won't automatically know why it burned unless you explicitly tell it.

Usually, when we try to fix these robots, we just give them a longer list of instructions or hope they "figure it out" by looking at their past successes and failures like a simple scorecard (e.g., "I succeeded 3 times, failed 2 times, so I'm 60% good"). The problem is, that scorecard is often misleading. A failure might have been a fluke, or a success might have been lucky.

Bayesian-Agent is a new framework that changes how we manage these robot assistants. Instead of just counting wins and losses, it treats every instruction or "skill" the robot uses as a scientific hypothesis that needs to be tested and updated with real evidence.

Here is how it works, using simple analogies:

1. The "Skill Library" as a Hypothesis Book

Imagine the robot has a library of "skills" (like "how to open a file" or "how to check a bank balance").

Old Way: The robot just adds new tips to the library whenever it makes a mistake, hoping the next time goes better. It's like writing a new rule in a notebook based on a gut feeling.
Bayesian-Agent Way: Every skill in the library is treated like a hypothesis. The system asks: "Given the specific situation we are in, how likely is this skill to work?" It doesn't just count "1 success, 1 failure." It builds a belief profile for each skill, tracking exactly when and why it works or fails.

2. The "Detective" Logic (The Posterior)

The system uses a method called Bayesian inference. Think of this as a detective who updates their theory as new clues arrive.

The Clues: Every time the robot tries a task, the system records the "verified trajectory." This means it doesn't just listen to the robot's self-report ("I think I did it right!"); it checks the actual result (e.g., "Did the file actually open?").
The Update: If a skill fails twice in a row under the same conditions, the detective updates the "belief" that this skill is broken for that specific situation. If it works three times, the belief that it is reliable grows stronger.

3. The Five "Actions" (The Mechanic's Toolkit)

Based on these updated beliefs, the system doesn't just "fix" things randomly. It has a specific set of tools to manage the skill library, much like a mechanic managing a car's parts:

Explore: If the robot has never tried a skill before, the system says, "Let's try it and see what happens."
Patch: If the robot fails the same way twice (e.g., it always forgets to save the file), the system adds a specific "guardrail" or reminder to the instructions to stop that specific error.
Split: If a skill is too broad (e.g., "Handle all bank transactions") and fails in some cases but works in others, the system splits it into two smaller, more specific skills.
Compress: If a skill is very reliable and works perfectly, the system shortens the instructions to save space, making the robot faster.
Retire: If a skill fails too often and the evidence shows it's unreliable, the system throws it in the trash so the robot stops trying to use it.

4. The Results: Fixing the "Burnt Cake"

The researchers tested this system on three different types of tasks:

SOP-Bench: Following complex, step-by-step business procedures.
Lifelong AgentBench: Doing a long series of tasks where you need to remember what happened earlier.
RealFin-Bench: Solving financial reasoning problems where some information might be missing.

What happened?

The "Repair" Mode: They took a robot that had already failed some tasks, fed the evidence into Bayesian-Agent, and let it "patch" the instructions.
- On the business procedure test, it fixed the failures and reached 95% success.
- On the long-series test, it fixed the failures and reached 100% success.
- On the financial test, it improved success from 45% to 65%.
The "From Scratch" Mode: They let the robot learn entirely from scratch using this system. It did well, but sometimes the "learning while doing" was a bit messy, showing that sometimes it's better to have a solid baseline first and then apply the "patches."

5. Why This Matters

The paper argues that building better AI agents isn't just about making the AI smarter (changing its brain/weights). It's about optimizing the environment it works in.

Think of it like this: If you have a great driver (the AI model), but the road signs are confusing, the map is wrong, or the car has a loose steering wheel (the "harness"), the driver will crash. Bayesian-Agent doesn't try to retrain the driver's brain; it fixes the road signs, updates the map, and tightens the steering wheel based on verified evidence of where the car went wrong.

In short: Bayesian-Agent turns the messy process of "trying and hoping" into a structured, auditable process of "testing, believing, and fixing," ensuring that the robot's instructions evolve based on facts, not just guesses.

Technical Summary: Bayesian-Agent: Posterior-Guided Skill Evolution for LLM Agent

1. Problem Statement

Large Language Model (LLM) agents increasingly rely on external inference environments—comprising prompts, tools, memory, Standard Operating Procedures (SOPs), and harness feedback—rather than model weights alone to solve tasks. While these reusable assets can improve execution without retraining, current methods for updating them often rely on heuristic reflection or simple frequency counts of success and failure.

The paper identifies two primary limitations in existing approaches:

Uncalibrated Updates: Treating sparse agent trajectories as independent, identically distributed (i.i.d.) observations leads to noisy edits. A skill might be reliable in one context but harmful in another; simple counting fails to capture this nuance.
Externalized Failure: When capabilities are externalized into skills and SOPs, failures are also externalized. If an agent updates assets based solely on natural-language self-critique, it may repair a current failure while introducing edits that degrade performance on future tasks. Conversely, if the harness never revises skills, repeated failures remain outside the model's learning loop.

The core challenge is how to maintain the external decision environment (the "harness") such that reusable skills and SOPs evolve based on verified evidence rather than uncalibrated trial and error.

2. Methodology: Bayesian-Agent

The authors introduce Bayesian-Agent, a framework that treats reusable skills and SOPs as evidence-bearing hypotheses. Instead of asking an LLM to decide if a skill is "good," the framework asks a Bayesian question: Given a frozen model and a specific inference environment, what should we believe about this skill after combining prior assumptions with verified evidence?

2.1 Problem Formulation

The framework fixes the model weights ( $M_\theta$ ) and treats the harness evolution as an optimization over the inference conditions ( $C_t$ ). The reliability of a skill $h_k$ is defined as the probability of success given the model, context, and observed features:
$p_{k,t} = P(y_t = 1 \mid M_\theta, C_t, h_k, z_t)$
where $z_t$ is a discrete feature vector extracted from a verified trajectory (e.g., token counts, turn counts, failure modes).

2.2 Trajectory Evidence

Bayesian-Agent updates beliefs only from verified trajectories ( $e_t$ ) generated by an execution harness. These trajectories include:

Task context and outcome ( $y_t \in \{0, 1\}$ ) determined by an external verifier or benchmark grader, not the model's self-assessment.
Runtime signals (token cost, latency, turn count) discretized into fixed buckets to handle sparse online datasets.
Failure modes derived from the verifier.

2.3 Bayesian Evidence Model

The system maintains a feature-conditioned categorical Bayesian evidence model for each skill:

Priors: Uses Laplace smoothing to provide conservative estimates when observations are sparse.
Likelihood: Calculates the probability of success/failure conditioned on specific feature values (e.g., "failure mode X occurs in context Y").
Posterior: Computes a success probability ( $s_{k,t}$ ) used for ranking and decision-making.
Summary: Maintains a conjugate Beta-Bernoulli summary ( $\alpha, \beta$ ) for audit and failure-dominance checks.

2.4 Posterior-Guided Skill Actions

The posterior state drives a conservative rewrite policy that maps belief states to five inspectable actions:

Explore: Triggered when no observations exist or the posterior is uncertain.
Patch: Triggered when the same failure mode appears at least twice (converting repeated failures into guardrails).
Split: Triggered when a broad skill covers heterogeneous cases (3+ contexts, 4+ observations).
Compress: Triggered when a skill is reliable (success $\ge$ 0.72) to keep context concise.
Retire: Triggered when failure evidence dominates (low success probability, high $\beta$ ).

Crucially, the framework separates posterior audit information (stored for debugging) from model-facing instructions. The LLM receives executable guardrails and failure-mode patches, not raw probability numbers.

2.5 Execution Modes

Full Mode: The registry evolves online from scratch during a benchmark run.
Incremental Mode: The system ingests verified traces from a completed baseline run, updates the registry, and reruns only the failed tasks with posterior-guided patches.

3. Key Contributions

Formulation of Skills as Hypotheses: Shifts self-evolution from empirical prompt accumulation to verified, posterior-guided optimization under uncertainty.
Unified Framework: Provides a unified Bayesian view for prompt, context, and harness engineering, instantiated with an efficient categorical evidence model and a posterior-guided rewrite policy.
Native and Cross-Harness Support: Introduces a minimal native backend while defining an adapter boundary that allows external harnesses (GenericAgent, mini-swe-agent, Claude Code) to utilize the same trajectory-evidence loop.
Empirical Validation: Conducts extensive studies on SOP-Bench, Lifelong AgentBench, and RealFin-Bench using DeepSeek models, comparing baseline, full Bayesian, and incremental repair variants.

4. Experimental Results

The paper evaluates Bayesian-Agent across three benchmarks and multiple backends (Native, GenericAgent, mini-swe-agent, Claude Code) using DeepSeek-v4-flash and DeepSeek-v4-pro.

4.1 Performance Gains

Incremental Repair: The incremental mode (repairing only failed tasks) showed significant improvements:
- SOP-Bench: Improved from 80% (GA) to 95%.
- Lifelong AgentBench: Improved from 90% (GA) to 100%.
- RealFin-Bench: Improved from 45% (GA) to 65%.
Token Efficiency: The incremental approach was highly token-efficient, using only 153k tokens to repair SOP-Bench failures compared to the full baseline run.
Backend Agnosticism: The framework successfully improved performance across different backends (Native, GenericAgent, mini-swe-agent, Claude Code), confirming that the benefit comes from the evidence loop rather than a specific runtime.

4.2 Limitations Observed

Full Mode Instability: In the Lifelong AgentBench setting with DeepSeek-v4-flash, the Full Bayesian mode (85%) underperformed the baseline GA (90%). This suggests that online skill evolution can introduce negative ordering effects or costs when evidence is still sparse.
Saturation: In settings where the baseline model already achieved 100% accuracy (e.g., SOP-Bench with DeepSeek-v4-pro), the Bayesian layer had no failures to repair, rendering the incremental mode inactive.

5. Significance and Claims

The paper claims that agent skill evolution is best viewed as posterior-guided harness optimization rather than uncalibrated prompt accumulation.

Auditability: By treating skills as hypotheses with explicit posterior states, the framework makes the evolution process inspectable. Users can see why a skill was patched, split, or retired based on specific failure modes.
Uncertainty Calibration: The approach explicitly handles the sparsity and context-dependency of agent trajectories, avoiding the pitfalls of treating sparse data as reliable frequency counts.
Practical Repair: The incremental repair setting demonstrates that a harness can spend additional inference resources specifically on failed cases to convert observed failure modes into reusable context, significantly boosting final accuracy without re-running the entire benchmark.

The authors conclude that while the approach is not a panacea for one-off tasks or non-stationary environments, it provides a robust, evidence-calibrated mechanism for improving reusable agent skills in settings with verifiers and recurring failure modes.