MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization

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.