# MOCHA: Multi-Objective Chebyshev Annealing for Agent Skill Optimization

arXiv: https://arxiv.org/abs/2605.19330 · HTML: https://mlsanity.com/paper/2605.19330/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Agent skill learning and evolution, one of 16 directions in LLM agents and tool use.
- Builds on 26 of its 36 references that are in the map.
- First posted on arXiv 19 May 2026.

## Placed in

- LLM agents and tool use / [Agent skill learning and evolution](https://mlsanity.com/agents/agent-skill-learning-and-evolution/)

## Builds on (most cited first, 26 of 26)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [FEVER: a large-scale dataset for Fact Extraction and VERification](https://mlsanity.com/paper/1803.05355/) (2018)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Eureka: Human-Level Reward Design via Coding Large Language Models](https://mlsanity.com/paper/2310.12931/) (2023)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [Meta-Harness: End-to-End Optimization of Model Harnesses](https://mlsanity.com/paper/2603.28052/) (2026)
- [Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs](https://mlsanity.com/paper/2406.11695/) (2024)
- [SkillRL: Evolving Agents via Recursive Skill-Augmented Reinforcement Learning](https://mlsanity.com/paper/2602.08234/) (2026)
- [TextGrad: Automatic "Differentiation" via Text](https://mlsanity.com/paper/2406.07496/) (2024)
- [HoVer: A Dataset for Many-Hop Fact Extraction And Claim Verification](https://mlsanity.com/paper/2011.03088/) (2020)
- [TheoremQA: A Theorem-driven Question Answering dataset](https://mlsanity.com/paper/2305.12524/) (2023)
- [Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2006.05078/) (2020)
- [Arithmetic Control of LLMs for Diverse User Preferences: Directional Preference Alignment with Multi-Objective Rewards](https://mlsanity.com/paper/2402.18571/) (2024)
- [Beyond One-Preference-Fits-All Alignment: Multi-Objective Direct Preference Optimization](https://mlsanity.com/paper/2310.03708/) (2023)
- [DebugBench: Evaluating Debugging Capability of Large Language Models](https://mlsanity.com/paper/2401.04621/) (2024)
- [Trace is the Next AutoDiff: Generative Optimization with Rich Feedback, Execution Traces, and LLMs](https://mlsanity.com/paper/2406.16218/) (2024)
- [Smooth Tchebycheff Scalarization for Multi-Objective Optimization](https://mlsanity.com/paper/2402.19078/) (2024)
- [Multi-Objective Alignment of Large Language Models Through Hypervolume Maximization](https://mlsanity.com/paper/2412.05469/) (2024)

## Built on by (most cited first, 1 of 1)

- [MOAE: Multi-Objective Agent Evolution with Pareto-Preserving Search](https://mlsanity.com/paper/2609.05992/) (2026)

## Abstract (arXiv)

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.