MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization

Abstract: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.

Preprint. 24 pages, 20 figures, 6 tables

Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Software Engineering (cs.SE)

I.2.7; I.2.6; I.2.4; I.2.8

arXiv:2605.19330 [cs.AI]

(or arXiv:2605.19330v2 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2605.19330 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.