AgentSkillOS: Managing AI Agent Skills Like an Operating System

Paper: 2603.02176 Authors: Hao Li, Chunjiang Mu, Jianhao Chen, Siyue Ren, Zhiyao Cui, Yiqun Zhang, Lei Bai, Shuyue Hu Categories: cs.CL

The Gap

AI agents now have access to hundreds of thousands of skills—tools for everything from data analysis to video editing. But here’s the problem: existing approaches treat skills like a flat list. When you have 200,000 skills, finding the right ones becomes impossible. Prior work either uses naive keyword search (which fails at scale) or assumes you already know which skills you need (which defeats the purpose). Nobody has tackled the fundamental question: how do you organize, discover, and compose skills when the ecosystem grows beyond human comprehension?

The paper identifies two specific failures in current systems: (1) retrieval bottleneck—flat skill lists make discovery O(n) expensive and semantically shallow, and (2) composition blindness—agents invoke skills one-at-a-time without understanding how to chain them into multi-step workflows.

Problem: Skill chaos at scale (200K+ skills, flat organization)
   |
   v
Assumption: Structure enables both discovery and composition
   |
   v
Method: Tree-based categorization + DAG-based orchestration
   |
   v
Evidence: Tree retrieval ~= oracle selection; DAG >> flat invocation
   |
   v
Conclusion: Hierarchical organization unlocks skill ecosystem potential

The Increment

One sentence: Before this paper, agents drowned in flat skill lists and invoked tools one-by-one; after, they navigate hierarchical skill trees and compose multi-tool pipelines automatically.

Core Mechanism

AgentSkillOS operates in two stages. First, the “Manage Skills” stage takes a chaotic pile of skills and recursively organizes them into a capability tree. Think of it like building a library classification system: start with broad categories (data processing, content creation), then recursively subdivide each node until individual skills sit at the leaves. Each node gets a semantic description, and the tree structure itself becomes a search index.

Second, the “Solve Tasks” stage uses this tree for intelligent retrieval and orchestration. When a task arrives, the system doesn’t search all 200K skills—it traverses the tree, pruning irrelevant branches early. Once it identifies candidate skills, it doesn’t just pick one; it constructs a DAG (directed acyclic graph) that chains multiple skills together. Each node in the DAG is a skill execution, and edges represent data dependencies. The system reasons about which skills to invoke, in what order, and how to route outputs between them.

Stage 1: Manage Skills              Stage 2: Solve Tasks
                                    
  [Flat skill pile]                 [User task]
         |                                |
         v                                v
  Recursive categorize            Tree-based retrieval
         |                          /           \
         v                         v             v
    Capability tree           [Skill A]      [Skill B]
    /     |     \                  \           /
  Cat1  Cat2  Cat3                  v         v
  / \    |    / \              DAG orchestration
S1  S2  S3  S4  S5                   |
                                     v
                                [Final output]

Here’s the structural metaphor: AgentSkillOS works like a city’s infrastructure system. The capability tree is the road network—highways branch into streets, streets into alleys, and you can navigate from “transportation” down to “bicycle repair shop” without checking every business in the city. The DAG orchestration is the supply chain—when you order a pizza, the system doesn’t just call one shop; it coordinates flour delivery, dough preparation, baking, and delivery in a dependency graph. Each step waits for its inputs, and the whole pipeline executes in parallel where possible. Without the road network, you’d wander randomly. Without the supply chain, you’d make a hundred phone calls yourself.

Key Concepts

• Capability Tree: Imagine you’re organizing a toolbox with 200,000 tools. You could dump them in a pile, but then finding a Phillips-head screwdriver takes forever. Instead, you build nested drawers: “Fastening” contains “Screwdrivers” which contains “Phillips” which contains individual sizes. That’s a capability tree. Each node is a category with a semantic description, and skills live at the leaves. The key insight: you can search by traversing the tree, checking only relevant branches. If you need image editing, you never look inside the “audio processing” subtree. This turns O(n) search into O(log n) traversal.

• DAG-based Orchestration: Most agents invoke skills sequentially: call skill A, get result, call skill B with that result. But complex tasks need parallel execution and dependency management. A DAG (directed acyclic graph) represents this explicitly: nodes are skill invocations, edges are data flows. If skill C needs outputs from both A and B, the DAG shows that A and B can run in parallel, then C waits for both. Concrete example: creating a video thumbnail requires (1) extracting a frame, (2) generating a title overlay, then (3) compositing them. Steps 1 and 2 are independent (parallel), step 3 depends on both (sequential). The DAG captures this structure, enabling efficient execution.

• Recursive Categorization: How do you build the capability tree in the first place? You can’t manually sort 200K skills. Recursive categorization works like this: given a set of skills, ask an LLM to propose high-level categories. Assign skills to categories. For each category with too many skills (say, >100), recursively subdivide it. Stop when each leaf node has a manageable number of skills. It’s like organizing files: if a folder has 10,000 items, you create subfolders by date, project, or type, then recursively subdivide those. The result is a balanced tree where no node is overwhelming.

Framework Shift

Before (mainstream approach):        After (this paper):

[Flat skill list]                    [Hierarchical tree]
  Skill_1                                  Root
  Skill_2                               /   |   \
  Skill_3                            Cat1 Cat2 Cat3
  ...                                / \   |   / \
  Skill_200000                     S1 S2  S3 S4 S5
      |                                    
      v                            [Task] 
  Linear search                       |
      |                               v
      v                          Tree traversal
  Single invocation                   |
      |                               v
      v                          DAG pipeline
  [Output]                        /   |   \
                                 v    v    v
                              [Skill executions]
                                     |
                                     v
                                 [Output]

From unstructured skill hoarding to structured skill orchestration, the core shift is treating skills as a composable ecosystem rather than a flat toolbox.

Expert Assessment

Problem choice: This is a real gap, not manufactured. The agent skill explosion is happening right now—Claude, GPT, and other platforms are accumulating thousands of tools. The paper correctly identifies that nobody has solved organization and composition at scale. It sits at the intersection of tool-use agents and software engineering (dependency management, modular composition), which is timely.

Method maturity: The tree-based retrieval is straightforward—almost obvious in hindsight, which is a good sign. The DAG orchestration is borrowed from workflow systems but applied cleverly to agent skills. There’s no deep algorithmic novelty here, but that’s fine; the contribution is recognizing that existing techniques (hierarchical indexing, dependency graphs) solve the agent skill problem. One concern: the recursive categorization relies heavily on LLM quality. If the LLM produces bad categories, the whole tree collapses.

Experimental integrity: The benchmark is solid—30 tasks across five domains, with artifact-based evaluation (actual outputs, not just text). Using Bradley-Terry for aggregation is appropriate. However, the baselines are weak. They compare against “flat invocation” and “native agent,” but where’s the comparison to vector-based retrieval (embed all skills, retrieve via similarity)? That’s the obvious alternative, and its absence is suspicious. The experiments show tree retrieval approximates oracle selection, but “oracle” here means “human-selected skills,” not “optimal skills.” The numbers look good (DAG substantially outperforms flat), but I’d want to see failure cases.

Writing quality: The abstract and introduction are clear. The method section is dense—too much notation for what’s conceptually simple. Figure quality is mediocre; the diagrams don’t illuminate the mechanism as well as they could. The related work section is thin; they don’t engage deeply with prior work on tool retrieval or workflow systems. If they rewrote Section 3 (method) with more intuition and fewer symbols, the paper would be much stronger.

Verdict: weak accept — Addresses a real problem with a sensible solution, but the execution is workmanlike rather than inspired, and the experimental evaluation leaves obvious gaps.

Takeaways

Practitioners can steal three concrete ideas:

1. Hierarchical skill indexing: If you’re building a tool-use system, don’t store tools in a flat list or rely solely on vector embeddings. Build a category tree (manually or via LLM-assisted clustering) and use it for coarse-grained filtering before fine-grained retrieval. This is cheap to implement and scales logarithmically.

2. Explicit dependency graphs for multi-tool tasks: Stop invoking tools sequentially in a loop. Represent multi-step workflows as DAGs where nodes are tool calls and edges are data dependencies. This enables parallelism, makes debugging easier (you can visualize the execution plan), and clarifies what depends on what.

3. Benchmark design for agent outputs: The paper’s evaluation approach—generate artifacts (videos, documents, visualizations), then use LLM-based pairwise comparison + Bradley-Terry aggregation—is a practical template for evaluating agent systems where outputs are complex and subjective. It’s more rigorous than single-judge scoring but cheaper than human evaluation at scale.

The meta-lesson: when your system accumulates too many components (skills, tools, APIs), don’t just throw embeddings at it. Add structure—hierarchies for discovery, graphs for composition. The paper doesn’t invent new algorithms; it shows that old ideas (trees, DAGs) solve new problems (agent skill chaos).