💬 NLP

SkillMAS: Skill Co-Evolution with LLM-based Multi-Agent System

SkillMAS is a non-parametric framework that simultaneously couples skill evolution with multi-agent system restructuring through utility learning, bounded skill refinement, and evidence-gated reorganization to overcome adaptation bottlenecks and enable effective post-deployment specialization across diverse tasks.

Original authors: Shuai Pan, Yixiang Liu, Jiaye Gao, Te Gao, Weiwen Liu, Jianghao Lin, Zhihui Fu, Jun Wang, Weinan Zhang, Yong Yu

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shuai Pan, Yixiang Liu, Jiaye Gao, Te Gao, Weiwen Liu, Jianghao Lin, Zhihui Fu, Jun Wang, Weinan Zhang, Yong Yu

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 team of expert workers (a "Multi-Agent System") built to solve complex problems, like organizing a house, fixing a computer, or managing a store. Usually, when these teams make mistakes, we try to fix them in two separate ways:

Teaching the workers new tricks: We give them better instructions or new tools (Skill Evolution).
Changing the team structure: We hire more people, fire the wrong ones, or change who reports to whom (MAS Restructuring).

The Problem:
The paper argues that doing these two things separately is a recipe for disaster. It's like a chef learning to cook a perfect steak (Skill) while the restaurant manager keeps changing the kitchen layout and the number of chefs (Structure) without talking to the chef.

If the chef gets a new, fancy knife but the kitchen is too small, the new skill is useless.
If the manager hires a new sous-chef but the old chef hasn't learned how to use the new equipment, the new hire is just confused.

This separation creates "bottlenecks" where the team gets stuck, overwhelmed, or confused about who is supposed to do what.

The Solution: SkillMAS
The authors introduce SkillMAS, a system that treats learning new skills and changing the team structure as one single, connected conversation. Instead of fixing them separately, SkillMAS looks at the team's actual performance record (verified traces) to decide what to do next.

Here is how it works, using a simple analogy:

1. The "Scorecard" (Utility Learning)

Imagine a strict manager who only gives credit based on proof.

If a worker tries a new trick and it works, the manager writes it down as a "Success."
If a worker tries a trick but fails, the manager notes exactly why it failed.
Crucially: The manager doesn't give credit just because a worker tried something. They only give credit if the worker actually did it and it worked. This prevents the team from hoarding useless "skills" that were just guessed at.

2. The "Toolbox Update" (Bounded Skill Evolution)

When the team fails, SkillMAS doesn't just throw a million new instructions at the workers. It acts like a careful editor:

It looks at the failure and asks: "Was this a simple mistake, like forgetting a step?" If yes, it fixes that one step.
It asks: "Was this a broken tool?" If yes, it sharpens the tool.
The "Bounded" part: It refuses to add a new skill unless it is absolutely necessary and proven to work. It prevents the toolbox from becoming a messy junk drawer full of half-baked ideas.

3. The "Team Reorg" (Evidence-Gated Restructuring)

This is the paper's biggest innovation. The system only changes the team structure (hiring/firing/merging) when the evidence proves the current structure is the problem.

Scenario A: The team fails because they don't know how to do a task. -> Fix: Teach them a new skill. Don't change the team.
Scenario B: The team fails because there are too many people trying to do the same job, or one person is trying to do too many different jobs. -> Fix: Split the team. Hire a specialist.
The Gate: The system won't reorganize the team unless the "Scorecard" shows that the current team layout is the specific cause of the failure. It avoids unnecessary drama and constant re-hiring.

Real-World Examples from the Paper

The authors tested this on three different "workplaces":

The Virtual House (ALFWorld): Imagine a robot trying to clean a messy room.
- Result: The system realized the robot was getting confused between "looking for an object" and "picking it up." It didn't just teach the robot better; it split the job into two specialized workers: a "Searcher" and a "Mover." This boosted success rates significantly.
The Computer Terminal (Lifelong Agent Bench): Imagine a worker fixing computer files.
- Result: The system created a specialist for "text logs" and another for "file permissions." It stopped one person from trying to do everything, which reduced errors.
The Retail Store (τ-Bench): Imagine a customer service agent handling returns and exchanges.
- Result: Surprisingly, the system decided not to split the team. It realized that for this specific job, having one highly skilled manager was better than having a committee. It improved the single manager's skills instead of adding more people. This proves the system is smart enough to know when not to restructure.

The Bottom Line

SkillMAS is a framework that says: "Don't just teach the team new tricks, and don't just shuffle the deck. Look at the evidence. If the problem is a lack of skill, teach. If the problem is a bad team structure, reorganize. But make sure you only do one when the other is actually the bottleneck."

By keeping the "learning" and the "organizing" tied together with hard evidence, the system avoids the confusion and inefficiency that happens when these two processes are left to run on their own.

Technical Summary: SkillMAS

1. Problem Statement

The paper addresses a critical limitation in current Large Language Model (LLM) agent systems: the adaptation decoupling between skill evolution and Multi-Agent System (MAS) restructuring.

Existing approaches typically treat these two adaptation targets as separate problems. One line of work focuses on evolving reusable skills or distilling trajectory lessons without simultaneously adjusting executor boundaries. Another line focuses on MAS organization (spawning agents, updating roles, or selecting topologies) without dynamically refining the underlying skill library. The authors argue this separation creates three recurring failure modes:

Redundant Evidence: Verified execution traces may introduce low-value evidence for skill evolution if the context is not properly managed.
Routing Overload: Skill evolution can make MAS organization harder to route and maintain, leading to context pressure and mis-specialization.
Structural Lag: Fixed MAS organizations can lag behind changing task structures or runtime complexity, becoming bottlenecks even if skills improve.

Without a shared evidence surface, the system cannot determine whether the next necessary intervention is skill evolution, MAS restructuring, or no change at all.

2. Methodology: SkillMAS

SkillMAS is a non-parametric framework designed to couple skill evolution with MAS restructuring using a shared verified-trace evidence surface. It does not retrain the underlying language models. Instead, it operates in discrete adaptation rounds where the system executes episodes, learns utility, and applies bounded updates.

2.1 Core Components

The framework maintains a round state $X_r$ comprising the skill library ( $L_r$ ), executor set ( $A_r$ ), Skill Utility ( $Q^s_r$ ), Executor Utility ( $Q^a_r$ ), a validation pool ( $P_r$ ), and a policy-derived expert index ( $K_r$ ).

A. Utility Learning

SkillMAS assigns credit based strictly on verified execution traces rather than retrieval alone.

Skill Utility ( $Q^s$ ): Updated only for skills that are explicitly invoked or supported by the executor-local trace slice.
Executor Utility ( $Q^a$ ): Updated only for executors that participated in verified execution.
Mechanism: The system uses a Monte Carlo credit-assignment rule. A skill is only credited if the trace confirms its usage (guard-and-step pattern match). This prevents assigning positive credit to merely retrieved but unused skills. Update rates decay automatically based on the count of prior verified updates for a specific entry.

B. Bounded Skill Evolution

Retained evidence (filtered for repeated failures, near misses, and reusable successes) drives bounded edits to the skill library.

Diagnosability: A failure trace is mapped to a dominant cause (e.g., missing precondition, incorrect order).
Bounded Updates: The system proposes local repairs only if the cause is uniquely identifiable. Allowed actions include add-guard, reorder-step, tighten-retrieval, or split-skill.
Constraints: Proposals are consolidated against the existing library to avoid unfiltered growth. New or heavily revised skills are held in a validation pool ( $P_r$ ) until sufficient usage evidence is gathered.

C. Evidence-Gated MAS Restructuring

MAS restructuring (adding, merging, or modifying executors) occurs only when retained failures and Executor Utility indicate a structural mismatch.

Trigger: Restructuring is gated by evidence such as high uncertainty among similar executors, repeated failures concentrated in a task family after skill repair, or broad executors owning mutually interfering skill clusters.
Action: The system can keep, add, merge/remove, or modify responsibility boundaries.
Constraint: At most one restructuring edit is applied per round, and it is strictly justified by the retained evidence set.

3. Key Contributions

The paper makes three primary contributions:

Problem Formulation: It identifies and formalizes adaptation decoupling as a system-level problem in post-deployment specialization, arguing that skill evolution and MAS organization must be optimized jointly.
SkillMAS Framework: It introduces a non-parametric scaffold that unifies Utility Learning, bounded skill evolution, and evidence-gated MAS restructuring under a single verified-trace evidence surface.
Empirical Evaluation: It evaluates this scaffold across three distinct domains: embodied manipulation (ALFWorld), command-line OS workflows (Lifelong Agent Bench), and retail-service interaction ( $\tau$ -Bench).

4. Experimental Results

The authors evaluated SkillMAS against baselines including Direct LLM, ReAct, CDMem, and Traj-Bootstrap.

ALFWorld (Embodied Manipulation): SkillMAS achieved 94.0% success on the full unseen split (126/134 tasks), outperforming the strongest published reference score of 93.0% (Traj-Bootstrap).
- Ablation: Transplanting the final skill library into a seed MAS organization dropped performance to 68.7%, and using a specialized MAS with seed skills dropped it to 50.0%, demonstrating that mismatched components degrade performance.
- Trajectory: The system grew from 5 to 13 active skills and added specialized executors (search, manipulation, appliance) as needed.
Lifelong Agent Bench (OS Tasks): SkillMAS reached 76.7% success on the 150-task evaluation, compared to 70.0% for a rerun of Traj-Bootstrap.
- Trajectory: Success peaked at round 3 (78/100) with 10 active skills and 4 executors. Notably, round 4 maintained the skill count but saw a performance drop, suggesting that skill count alone is not a guarantee of success.
$\tau$ -Bench (Retail): SkillMAS achieved 70.2% on the official base set (114 tasks).
- Trajectory: Unlike other benchmarks, the best checkpoint here preserved a single-agent system. Expanding to a multi-agent setup with a "preflight executor" actually dropped performance (32/74), indicating that SkillMAS correctly chose not to restructure the MAS when it was unnecessary.

5. Significance and Claims

The paper claims that the central innovation is not the novelty of individual update targets (skill evolution or MAS restructuring exist in isolation in prior work), but the coupling of these targets via a shared evidence surface.

Attribution: The framework clarifies how post-deployment specialization is attributed, updated, and applied by ensuring credit is assigned only to execution-supported actions.
Adaptation Logic: It demonstrates that specialization is not uniformly beneficial; the system must be able to choose not to expand the MAS (as seen in $\tau$ -Bench) or to restructure it (as seen in ALFWorld) based on empirical evidence.
Limitations: The authors modestly note that the evidence is benchmark-local and protocol-dependent. They do not claim domain-agnostic superiority yet, acknowledging the lack of controlled frozen-target retraining ablations and formal significance tests for causal contributions. They also note that token/cost accounting is not yet fully characterized.

In summary, SkillMAS presents a mechanism for coupled adaptation, arguing that for LLM agents to improve after deployment, the evolution of their "tools" (skills) and their "organization" (MAS structure) must be coordinated through a shared, verified history of execution.