CoEvoSkill: Niche-Aware Co-Evolution of Skill Content and Graph Topology for Agents

Skill libraries have emerged as a lightweight adaptation for LLM agents, providing deployable tools without modifying model weights. However, existing methods optimize skill libraries along two isolated lines: refining individual skill content, or evolving graphs that organize skills. Moreover, neither line addresses the execution layer itself—refined skills can still be realized as invalid, repetitive, or premature steps. We argue that skill content, graph topology, and execution are mutually dependent. We present CoEvoSkill, a framework that closes this loop: skill texts are refined by failure attribution from execution, the dependency graph is updated by success-conditioned synergy scores, and a Monte Carlo Tree Search (MCTS) controller searches over graph-supported skills, with a guard that validates every language realization before it changes the state. The two layers exchange evidence: guard rejections and search statistics drive content edits, edge updates, and detection of missing skills, while evolved libraries reshape the candidate space the search sees. We prove a fixed-point theorem showing that the alternating optimization converges under bounded edits and contractive topology changes. Experiments across various domains such as web navigation, mathematical reasoning, financial analysis, and code generation show that CoEvoSkill outperforms state-of-the-art methods, at the same time exhibiting strong generalization capability.