Your AI Agent's Skill Files Are Probably Suboptimal — Here's How to Fix That Automatically

A bilevel optimization framework using Monte Carlo Tree Search treats agent skill design as a formal search problem — and lets LLMs improve their own operating instructions.

~5 min read · NUS / UC Berkeley / CUHK · 2026-04-21 · Agentic

TL;DR Agent "skills" — structured folders of instructions, tools, and reference materials that tell LLM agents how to approach a task — significantly affect performance, but no one has had a principled way to optimize them. This paper formulates skill optimization as a bilevel problem: an outer Monte Carlo Tree Search explores structural changes to the skill package, while an inner loop refines the content under each candidate structure. On an operations research QA benchmark, the framework improves agent accuracy from 0.906 to 0.9375.

Prompt engineering gets all the attention. But there's a quieter design decision that matters just as much for deployed LLM agents: the skill package — the folder of files that tells the agent what to do, what tools to use, and what reference material to consult. Get that wrong and your agent wastes context, gets misdirected, or quietly underperforms. Get it right and accuracy can jump meaningfully. The problem is that "getting it right" has mostly been artisanal.

This paper changes that.

💡 The Core Idea A skill has two separable dimensions: what components it contains and how they're organized (structure), and what those components actually say (content). These two dimensions interact — adding a new section to your instruction file might require moving details out to a reference file to stay within token limits. This interdependence is exactly the shape of a bilevel optimization problem: search over structures in the outer loop, refine content for each candidate structure in the inner loop.

What Is an Agent Skill?

An agent skill, as defined by Anthropic's Agent Skills specification, is a directory built around a central SKILL.md file. That file holds a YAML frontmatter block (metadata like routing description and approved tools) followed by Markdown instructions. Optional subdirectories add scripts (scripts/), reference documents (references/), and static assets (assets/).

The loading model is progressive: at startup the agent sees only lightweight metadata; upon activation it gets the full SKILL.md; subdirectory files load on demand. This hierarchy matters for optimization — it means not everything is equally "visible" to the agent at any given moment.

Think of it like a well-organized README versus a chaotic one. Both contain the same information, but one makes the right details immediately accessible to whoever (or whatever) is reading it.

The Bilevel Formulation

The authors represent a skill as a tuple S = (θ, ϕ), where θ is the structure configuration (what components exist and how they're arranged) and ϕ is the content instantiated under that structure.

Formally, they maximize:

$$\max_{\theta \in \Theta} \max_{\phi \in \Phi(\theta)} R_{S_0}(\theta, \phi)$$

In plain English: find the structure θ that, when paired with its best achievable content ϕ, produces the highest downstream task performance — subject to staying within the token budget and structural validity constraints.

The outer loop is where MCTS comes in. Structural edits are path-dependent — adding a checklist section early might make a later reorganization necessary or irrelevant. This is precisely the kind of sequential discrete decision-making that MCTS handles well: it explores multiple structural edit paths, uses delayed evaluation feedback (you only know if a structure was good after content refinement and evaluation), and balances exploration against exploitation.

The Outer Loop: MCTS Over Structures

flowchart LR
    A[Seed Skill S₀] --> B[Comprehension Stage]
    B --> C[Initial θ₀, ϕ₀, Profile P]
    C --> D{MCTS Selection}
    D --> E[Expansion: LLM proposes edit]
    E --> F{Validation Gate}
    F -->|Invalid| D
    F -->|Valid θ′| G[Inner Loop]
    G --> H[Reward r′]
    H --> I[Backpropagation]
    I --> D

The MCTS outer loop runs the standard four-phase cycle — selection, expansion, evaluation, backpropagation — with two adaptations. First, evaluation is bilevel: a structure can't be scored directly; it must be handed to the inner loop for content refinement first. Second, the expansion step is LLM-guided: a three-stage reasoning procedure (analyze current state → diagnose underperformance → propose a concrete structural edit) generates the next candidate.

The framework supports two selection policies. The default UCB1 policy works well when reward signals are stable. For noisier settings, a mixed-probability policy blends uniform exploration with score-weighted sampling, controlled by a mixing coefficient λ — providing a smooth dial between "explore broadly" and "exploit what's working."

The Inner Loop: Family-Aware Content Refinement

Once the outer loop proposes a new structure θ′, the inner loop needs to fill it with content. The first step is a bridge operation: transfer existing content into the new structure, preserving reusable material while accommodating added, removed, or reordered components.

Then comes family-specific refinement. Rather than applying a single generic editing procedure, the inner loop dispatches to one of five refinement families — metadata updates, routing text, instruction text, redistribution, or script editing — matched to the type of structural change that triggered it. This is a meaningful design choice: a reorganization of SKILL.md sections needs different refinement logic than the introduction of a new Python script.

The inner loop runs a bounded sequence of refinement attempts and selects the final output using a pessimistic criterion: it computes a lower confidence bound (LCB = δ̄ − t_crit · s/√k) on the observed improvement and prefers outcomes where this LCB is nonnegative — accepting gains only when the evidence is strong enough to survive uncertainty discounting.

What Happened in the Experiment

The team tested the framework on ORQA — a multiple-choice QA benchmark over operations research problems with 1,513 questions across 20 domains. The seed skill was a two-file package generated by a built-in skill-creator tool, providing a basic answering workflow and a reference on question types.

Two MCTS configurations were compared — a conservative (Config A: UCB1, 3 rounds) and an exploratory one (Config B: mixed-probability, 6 rounds). Both reached the same peak reward of 0.9434 on the search split. The tiebreaker was the confirmation split, where Config B scored 0.8857 versus Config A's 0.8571. Config B's winning skill scored 0.9375 on the held-out test split versus the seed skill's 0.90625 — a gain of +0.03125.

What did the search actually find? The MCTS tree explored several structural paths before converging on one key insight: the critical question-type guidance that lived in a separate reference file should be merged directly into SKILL.md, and a new "Question-Type Triage Checklist" section should be added. Centralizing this guidance meant the agent could access it without loading a secondary file — reducing the reasoning overhead and making the instruction surface more coherent.

Why It Matters

The contribution here isn't the accuracy improvement per se — 3 percentage points on one benchmark is modest. The value is the formalization. Skill design has been a craft; this paper proposes an algorithm.

For practitioners building production agent systems, this suggests a practical workflow: start with an AI-generated seed skill, run bilevel MCTS optimization over a held-out question sample, and let the search discover structural reorganizations that a human designer might miss. The framework is agnostic to the specific skill domain, which means it could plausibly generalize beyond OR questions to any structured skill package.

The bilevel separation also provides interpretability that single-level approaches (like optimizing code workflows directly) don't: when the search tree returns a winner, you can trace exactly which structural edits led there and understand why the content refinement improved things.

⚠️ Watch out for

• The experiment runs on a single benchmark with a modest sample size (120 questions total across search, confirm, and test splits), so generalization to other skill types is undemonstrated.
• Evaluation uses specific commercial models (openai/gpt-5.2-codex, openai/gpt-5.4) — results may not transfer to other agent backends.
• Optimization cost can be substantial: multiple MCTS rounds, each requiring inner-loop refinement and downstream evaluation, adds up quickly.
• The framework requires a pre-existing seed skill — it optimizes rather than discovers skills from scratch.

Go Deeper

• AFlow: Automating Agentic Workflow Generation — The closest prior work; also uses MCTS over agent artifacts, but on code-represented workflows rather than structured skill packages.
• SkillsBench: Benchmarking How Well Agent Skills Work Across Diverse Tasks — Provides the empirical motivation: skill quality is highly heterogeneous and significantly impacts downstream performance.

Source: Bilevel Optimization of Agent Skills via Monte Carlo Tree Search Authors: Chenyi Huang, Haoting Zhang, Jingxu Xu, Zeyu Zheng, Yunduan Lin Published: 2026-04-21 PDF: https://arxiv.org/pdf/2604.15709