MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization

MOCHA introduces Multi-Objective Chebyshev Annealing for Agent Skill Optimization, a framework that addresses the inherent trade-offs between task performance and platform constraints in skill specifications by employing principled multi-objective optimization techniques to navigate non-convex objective regions. The gist is that MOCHA breaks through on every task, achieving 7.5% relative improvement in mean correctness over the strongest baseline while discovering twice as many Pareto-optimal skill variants

Problem Formulation and Core Insight

Skill optimization is formalized as a structured multi-objective problem over multi-field natural-language artifacts subject to hard platform constraints (SKILL.md field limits), identifying competing objectives—task correctness and platform compliance—that existing single-objective optimizers collapse or ignore The paper identifies that skill optimization is a structured multi-objective problem that requires principled Pareto front navigation because the Pareto front of a skill can be non-convex, meaning linear methods cannot reach all optimal points. MOCHA solves this by using Chebyshev scalarization to cover the full Pareto front, including non-convex regions.

MOCHA Methodology

MOCHA structures each iteration around two stages (Algorithm 1), transitioning between exploration and exploitation modes via threshold annealing.

1. Stage 1 involves selecting a parent skill via randomized Chebyshev scalarization, where the cost is defined as sw(p) = max j∈[M] wj · mj (p) − z∗j to minimize the worst-case weighted deviation from the ideal point.

2. Stage 2 involves improving the front via mutation, using two acceptance modes: Exploration, which accepts a candidate if it improves the Pareto front in any direction irrespective of w used for parent selection, and Exploitation, which accepts a candidate only if it improves the front in the same direction as w.

3. The transition between modes is governed by threshold annealing, where Accept(p) = HVC(p,P) > τ (b) if τ (b) > 0 for exploration and sw(p) < sw(pparent) if τ (b) ≈ 0 for exploitation.

Evaluation and Results

The experiments were conducted across six diverse agent skills—Reasoning, Multi-hop, Code—using Claude Haiku 4.5 as the execution backbone and Claude Opus 4.6 as the reflection and mutation model. The key finding is that existing optimizers fail to improve on 4 of 6 tasks, with all three baselines returning the seed skill unchanged after 1000 rollouts. MOCHA breaks through on every task, achieving a 7.5% relative improvement in mean correctness over the strongest baseline and discovering twice as many Pareto-optimal skill variants.

Key Components of MOCHA

The framework incorporates several structured components to handle the multi-field nature of skills:

**: Compliance-aware mutation biases candidate generation toward the feasible region by receiving explicit format constraints and a per-field compliance status report. 3.2.4 Structured Mutation for Multi-Field Skills is introduced to ensure mutations respect the SKILL.md structure. 3.2.5 Metric Normalization maps objectives to [0, 1] using a linear scoring function for compliance where compliance(l) = max(0, 1 − l/L). The hypervolume reference point is set at the origin (0, 0, 0). The Hypervolume Contribution HVC(p,P) = HV(P ∪ p) − HV(P) is used as a unary quality measure to signal Pareto front expansion independent of scalarization weights. MOCHA's gains come purely from the candidate selection strategy, not from privileged mutation feedback. The final skill pool P grows as validated candidates are committed to, returning a set of all validated skill variants to the practitioner. MOCHA’s gains scale with objective conflict, as seen on FEVER (14.9% relative gain) and TheoremQA (10.4%) where instruction length pushes against body token limits. The results show that removing HVC gating favors exploitation for highest correctness, while removing annealing favors exploration for richest Pareto fronts. MOCHA provides the recommended default for balanced operation. MOCHA’s gains scale with objective conflict, as seen on FEVER (14.9% relative gain) and TheoremQA (10.4%) where instruction length pushes against body token limits. The core finding is stark: on 4 of 6 tasks, all three baselines return the seed skill unchanged after 1000 rollouts—single-objective selection strategies simply cannot escape the initial prompt, even when given the same multi-objective feedback during mutation. The paper concludes that MOCHA’s Chebyshev scalarization breaks through this barrier, achieving 7.5% relative improvement in mean correctness over the strongest baseline, with gains up to 14.9% on FEVER and 10.4% on TheoremQA where objective conflict is strongest. The paper looks ahead to adaptive annealing, meta-harness optimization, and integration with skill discovery as a path toward end-to-end agent skill evolution. MOCHA’s gains scale with objective conflict, as seen on FEVER (14.9% relative gain) and TheoremQA (10.4%) where instruction length pushes against body token limits. The core finding is stark: on 4 of 6 tasks, all three baselines return the seed skill unchanged after 1000 rollouts—single-objective selection strategies simply cannot escape the initial prompt, even when given the same multi-objective feedback during mutation. The paper concludes that MOCHA’s Chebyshev scalarization breaks through this barrier, achieving 7.5% relative improvement in mean correctness over the strongest baseline, with gains up to 14.9% on FEVER and 10.4% on TheoremQA where objective conflict is strongest. The paper looks ahead to adaptive annealing, meta-harness optimization, and integration with skill discovery as a path toward end-to-end agent skill evolution. The core finding is stark: on 4 of 6 tasks, all three baselines return the seed skill unchanged after 1000 rollouts—single-objective selection strategies simply cannot escape the initial prompt, even when given the same multi-objective feedback during mutation. The paper concludes that MOCHA’s Chebyshev scalarization breaks through this barrier, achieving 7.5% relative improvement in mean correctness over the strongest baseline, with gains up to 14.9% on FEVER and 10.4% on TheoremQA where objective conflict is strongest. The paper looks ahead to adaptive annealing, meta-harness optimization, and integration with skill discovery as a path toward end-to-end agent skill evolution. The core finding is stark: on 4 of 6 tasks, all three baselines return the seed skill unchanged after 1000 rollouts—single-objective selection strategies simply cannot escape the initial prompt, even when given the same multi-objective feedback during mutation. The paper concludes that MOCHA’s Chebyshev scalarization breaks through this barrier, achieving 7.5% relative improvement in mean correctness over the strongest baseline, with gains up to 14.9% on FEVER and 10.4% on TheoremQA where objective conflict is strongest. The paper looks ahead to adaptive annealing, meta-harness optimization, and integration with skill discovery as a path toward end-to-end agent skill evolution.

1. Bold Header: Multi-Objective Skill Optimization (MOCHA) Framework

This framework replaces single-objective selection with Chebyshev scalarization—covering the full Pareto front, including non-convex regions, enabling optimization across competing objectives like task performance and platform limits.

2. Bold Header: Exploration and Exploitation Modes

The system transitions between two modes based on budget consumption: exploration (HVC gating) to exploitation (Chebyshev acceptance), which allows the optimizer to simultaneously expand the Pareto front and then refine the extremes.

3. Bold Header: Structured Mutation for Multi-Field Skills

The mutation step incorporates explicit platform constraints, as seen in the prompt template that includes a compliance status report, biasing candidate generation toward feasible regions by respecting limits like description character counts.

4. Bold Header: Comprehensive Pareto Front Discovery

The system can discover twice as many Pareto-optimal skill variants by utilizing the Hypervolume Contribution (HVC) to measure and rank candidates based on their unique contribution to the total objective space covered, rather than relying on single scalarization weights.

5. Bold Header: Domain-Specific, Rigorous Skill Protocols

The resulting optimized skills can incorporate complex reasoning structures; for instance, MOCHA discovers a 6-step expert verification protocol for GPQA that includes adversarial self-checking for common pitfalls.

LLM agents organize behavior through skills -- structured natural-language specifications that govern how an agent reasons, retrieves, and responds. Unlike monolithic prompts, skills are multi-field artifacts with platform limits: descriptions are indexed for routing, instruction bodies are loaded into a shared context window, and every extra line costs the agent context it could spend elsewhere. Skill optimization is therefore inherently multi-objective: a skill should be accurate and economical at once. Existing prompt optimizers collapse these goals into a single score, and we find that this makes them stall: in most of their runs, 1000 rollouts yield zero progress over the seed skill. We introduce MOCHA (Multi-Objective CHebyshev Annealing), which selects skills to improve by Chebyshev scalarization and accepts improvements that expand the Pareto front, annealing from exploration to exploitation. Chebyshev scalarization scores a skill by its largest weighted shortfall from a perfect skill; with random weights, it can select any skill on the Pareto front for improvement, including trade-offs that an average would never favor. Across six diverse skills and two models, MOCHA escapes the seed in nearly every run, achieving 7.9% higher mean accuracy than the strongest baseline (up to 23.7% on DebugBench with GPT 5.5 and 14.9% on FEVER with Claude Haiku 4.5) while discovering Pareto fronts with the highest hypervolume and nearly twice as many Pareto-optimal skills.